Вопрос по algorithm, combinations, permutation – Алгоритм перечисления всех уникальных перестановок чисел, содержащих дубликаты

4

Проблема заключается в следующем: учитывая набор чисел, которые могут содержать дубликаты, вернуть все уникальные перестановки.

Наивным способом является использование набора (в C ++) для хранения перестановок. Это занимаетO(n! & # XD7; журнал(n!)) время. Есть ли лучшее решение?

Так как естьn! перестановкиn различные целые числа, вы не можете сделать лучше, чемO(n!) если вам необходимо перечислить их. Также обратите внимание, что наличие дубликатов не имеет значения, поскольку процесс удаления дубликатов занимает незначительное количество времени по сравнению с перечислением перестановок. verdesmarald
1. next_permutation (в C ++ STL) посещает каждую перестановку ровно один раз, даже если есть дубликаты. 2. Требуемое пространство составляет O (nn!), not O(n!). 3. Inserting all n! permutations in an STL set would take O(n! log(n!)) = O(nп! * LOGN) bloops
@veredesmarald. Да, я пытаюсь уменьшить сложность времени до O (n!). stackunderflow
Звучит домашнее задание. Nicu Stiurca
@bloops Я считаю, что смысл упражнения заключается в реализацииnext_permutation, Также, возможно, мне следовало бы уточнить, что я имею в виду только временную сложность, и я бы просто сохранил их в списке (поскольку в следующем алгоритме Пермь уже исключены дубликаты). verdesmarald

Ваш Ответ

6   ответов
2

1) Некоторые вариации при поиске с возвратом назад / рекурсивный поиск обычно решают проблему такого рода. возвращающей список всех перестановок для (n-1) объектов, создайте список всех перестановок для n объектов следующим образом: для каждого элемента в списке вставьте n-й объект во все возможные позиции, проверяя наличие дубликатов. Это не особенно эффективно, но часто генерирует простой код для такого рода проблем.

2) Смотрите Википедию наhttp://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

3) Академики потратили много времени на детали этого. См. Раздел 7.2.1.2 Knuth Vol 4A - это большая книга в твердом переплете со следующим кратким оглавлением на Amazon:

Глава 7: Комбинаторный поиск 1

7.1: нули и единицы 47

7.2: Генерация всех возможностей 281

0

ров символов, k количество повторных символов в каждом наборе:

#include<iostream>
#include<cstring>

using namespace std;

const int MAX_CHARS_STRING=100;
int CURRENT_CHARS=0;
char STR[MAX_CHARS_STRING];

void myswap(int i, int j){
    char c=STR[i];STR[i]=STR[j];STR[j]=c;
}

bool IstobeExecuted(int start,int position){
    if(start==position)
        return true;
    for(int i=position-1;i>=start;i--){
        if(STR[i]==STR[position])
            return false;
    }
    return true;
}

void Permute(int start, int end,int& perm_no){
    if(end-start<=1){
        if(STR[end]==STR[start]){
            cout<<perm_no++<<") "<<STR<<endl;
            return;
        }
        cout<<perm_no++<<") "<<STR<<endl;
        myswap(start, end);
        cout<<perm_no++<<") "<<STR<<endl;
        myswap(start,end);
        return;
    }
    for(int i=start; i<=end;i++){
        if(!IstobeExecuted(start,i)){
            continue;
        }
        myswap(start,i);
        Permute(start+1,end,perm_no);
        myswap(start,i);
    }
}


int main(){
    cin>>STR;int num=1;
    Permute(0,strlen(STR)-1,num);
    return 0;
}

Надеюсь это поможет

0

который я придумал, подумав о том, как я выписал перестановки вручную и поместив этот метод в код, короче и лучше:

def incv(prefix,v):
  list = []
  done = {}
  if v:
    for x in xrange(len(v)):
      if v[x] not in done:
        done[v[x]] = 1
        list = list + incv(prefix+v[x:x+1],v[:x] + v[x+1:])
  else:
    list.append(''.join(prefix))
  return list

def test(test_string,lex_ord=False):
  if lex_ord:
    test_string = [x for x in te,st_string]
    test_string.sort()
  p = incv([],[x for x in test_string])
  if lex_ord:
    try_p = p[::]
    try_p.sort()
    print "Sort methods equal ?", try_p == p
  print 'All', ','.join(p), "\n", test_string, "gave", len(p), "permutations"

if __name__ == '__main__':
  import sys
  test(sys.argv[1],bool(sys.argv[2] if len(sys.argv) > 2 else False))

Notes

incv increments the permutation vector to find all of them. It also correctly handles repeat letters. test prints out all permutations and their count for the test string. It also makes sure that if you request lexicographic ordering that the sort before and sort after methods are the same. This should be True since the original string is ordered and the increment permutation function transforms the string into the next lexicographic string by the given alphabet.

скрипт может быть запущен из командной строки:

python script.py [test_string] [optional anything to use lexicographic ordering]

1

мой блог на этот вид перестановок (среди прочего), чтобы получить больше фона - и перейдите по некоторым ссылкам там.

Вот версия моего генератора лексикографических перестановок, созданного по образцу последовательности генераторов перестановок Steinhaus & # x2013; Johnson & # x2013; Trotter, которая выполняет требуемые действия:

def l_perm3(items):
    '''Generator yielding Lexicographic permutations of a list of items'''
    if not items:
        yield []
    else:
        dir = 1
        new_items = []
        this = [items.pop()]
        for item in l_perm3(items):
            lenitem = len(item)
            try:
                # Never insert 'this' above any other 'this' in the item 
                maxinsert = item.index(this[0])
            except ValueError:
                maxinsert = lenitem
            if dir == 1:
                # step down
                for new_item in [item[:i] + this + item[i:] 
                                 for i in range(lenitem, -1, -1)
                                 if i <= maxinsert]:
                    yield new_item                    
            else:    
                # step up
                for new_item in [item[:i] + this + item[i:] 
                                 for i in range(lenitem + 1)
                                 if i <= maxinsert]:
                    yield new_item                    
            dir *= -1

from math import factorial
def l_perm_length(items):
    '''\
    Returns the len of sequence of lexicographic perms of items. 
    Each item of items must itself be hashable'''
    counts = [items.count(item) for item in set(items)]
    ans = factorial(len(items))
    for c in counts:
        ans /= factorial(c)
    return ans

if __name__ == '__main__':
    n = [0, 1, 2, 2, 2]
    print '\nLexicograpic Permutations of %i items: %r' % (len(n), n)
    for i, x in enumerate(l_perm3(n[:])):
        print('%3i %r' % (i, x))
    assert i+1 == l_perm_length(n), 'Generated number of permutations is wrong'  

Выходные данные из вышеуказанной программы, например, следующие:

Lexicograpic Permutations of 5 items: [0, 1, 2, 2, 2]
  0 [0, 1, 2, 2, 2]
  1 [0, 2, 1, 2, 2]
  2 [2, 0, 1, 2, 2]
  3 [2, 0, 2, 1, 2]
  4 [0, 2, 2, 1, 2]
  5 [2, 2, 0, 1, 2]
  6 [2, 2, 0, 2, 1]
  7 [0, 2, 2, 2, 1]
  8 [2, 0, 2, 2, 1]
  9 [2, 2, 2, 0, 1]
 10 [2, 2, 2, 1, 0]
 11 [2, 1, 2, 2, 0]
 12 [1, 2, 2, 2, 0]
 13 [2, 2, 1, 2, 0]
 14 [2, 2, 1, 0, 2]
 15 [1, 2, 2, 0, 2]
 16 [2, 1, 2, 0, 2]
 17 [2, 1, 0, 2, 2]
 18 [1, 2, 0, 2, 2]
 19 [1, 0, 2, 2, 2]
0

Решение Paddy3118теперь он не рекурсивный, с ленивой оценкой (полностью основан на генераторах) и быстрее примерно на 30%.

def _handle_item(xs, d, t):
    l = len(xs)

    try:
        m = xs.index(t)
    except ValueError:
        m = l

    if d:
        g = range(l, -1, -1)
    else:
        g = range(l + 1)

    q = [t]
    for i in g:
        if i <= m:
            yield xs[:i] + q + xs[i:]

def _chain(xs, t):
    d = True

    for x in xs:
        yield from _handle_item(x, d, t)

        d = not d

def permutate(items):
    xs = [[]]

    for t in items:
        xs = _chain(xs, t)

    yield from xs

Постскриптум Я заметил, что Paddy3118 также использовал генераторы своей реализации, в то время как я работал против реализации в посте блога, которая более интенсивно использует память. Я отправляю это так или иначе, поскольку эта версия могла бы считаться более чистой.

4

Sort the list: O(n lg n) The sorted list is the first permutation Repeatedly generate the "next" permutation from the previous one: O(n! * <complexity of finding next permutaion>)

Шаг 3 может быть выполнен путем определения следующей перестановки как той, которая будет отображаться непосредственно после текущей перестановки, если список перестановок был отсортирован, например:

1, 2, 2, 3
1, 2, 3, 2
1, 3, 2, 2
2, 1, 2, 3
2, 1, 3, 2
2, 2, 1, 3
...

Нахождение следующей лексикографической перестановки - O (n), и простое описание дано на странице Википедии для перестановки под заголовкомГенерация в лексикографическом порядке. If you are feeling ambitious, you can generate the next permutation in O(1) using простые изменения

@bloops Похоже, вы правы. Я этого не знал, спасибо!
Следующая_пермутация - это точка. А летом домашней работы нет :) stackunderflow
@zwx Там, где я живу, зима. :) Я добавил несколько ссылок на следующие алгоритмы перми, если вы столкнетесь с какими-то конкретными трудностями, я с радостью помогу, но в противном случае я не вижу каких-либо преимуществ во мне, перепечатывая алгоритмы здесь.
Сложность "обычного"next_permutation алгоритм O (1) амортизируется по всем перестановкам. Поэтому, если вы посещаете все перестановки, это оптимально.
Обновлено: я изначально неправильно прочитал вопрос, и думал, что дубликаты должны быть отброшены до вычисления перестановок.

Похожие вопросы