Генерация всех лексикографических перестановок без сравнений элементов

Я столкнулся с проблемой, когда у меня есть заданная последовательность s=(a,b,c,d,e...) - отсортированная в порядке неубывания. Моя работа заключается в разработке алгоритма, который будет генерировать все возможные перестановки в лексикографическом порядке, заканчивающиеся на перевернутом s (наибольшем по порядку).

Хитрость в том, что я не могу сравнивать любые 2 элемента друг с другом. Все операции должны выполняться "автоматически", вне зависимости от значений элементов.


algorithm permutation lexicographic discrete-mathematics
person maciek    schedule 11.01.2015    source источник
comment
Либо вам нужно сравнить элементы, чтобы определить, какие из них равны, либо вам должно быть разрешено выводить повторяющиеся строки.   -  person aioobe    schedule 11.01.2015
comment
Хорошо, затем выполните перестановки 1..n и примените перестановку к s только при выводе. Но, возможно, это нарушает дух этого вопроса. Почему существует это ограничение?   -  person harold    schedule 11.01.2015
comment
Хорошо, я выведу повторяющиеся строки, если в s есть одинаковые элементы.   -  person maciek    schedule 11.01.2015
comment
@harold: я не понимаю твоего решения ... Не могли бы вы быть более точным?   -  person maciek    schedule 11.01.2015
comment
@maciek в дополнительном массиве вы генерируете все перестановки 1..n, вы можете сделать это стандартным способом, потому что никакие элементы из s не участвуют, поэтому ограничение на сравнения не применяется. Затем для каждой перестановки используйте ее для построения соответствующей перестановки элементов из s.   -  person harold    schedule 11.01.2015
comment
Все, что нужно, — это стандартный алгоритм генерации перестановок в лексикографическом порядке. Возможно, обычные/наивные алгоритмы генерируют перестановки в лексикографическом порядке?   -  person aioobe    schedule 11.01.2015
comment
Как вы определяете лексикографический порядок в этой задаче? Стандартное определение требует, чтобы элементы были сопоставимы.   -  person kraskevich    schedule 11.01.2015
comment
@harold: На самом деле мои элементы {a,b,c...} представляют собой целые числа {1,2,3...}, что не является решением, которое я ищу. Я ищу другой алгоритм, а не ярлык.   -  person maciek    schedule 11.01.2015
comment
@aioobe: как я вижу, все эти стандартные алгоритмы включают сравнение значений элементов - вот в чем проблема.   -  person maciek    schedule 11.01.2015
comment
@ILoveCoding: порядок определяется как обычно, элементы сопоставимы. Алгоритм не должен их сравнивать. Я начинаю с самой низкой перестановки, заканчиваю самой высокой. Алгоритм должен менять местами элементы независимо от их значений.   -  person maciek    schedule 11.01.2015
comment
Взгляните на rosettacode.org/wiki/Permutations_by_swapping. Имейте в виду, что на основе ваших данных {1, 2,3...} можно составить список пар {(1,a),(2,b),(3,c),...}, где сопутствующий элемент сравним.   -  person aioobe    schedule 11.01.2015
comment
Спасибо @aioobe, я это уже видел - это не по порядку.   -  person maciek    schedule 11.01.2015

Ответы (1)


arrow_upward
1
arrow_downward

Вы можете сделать это следующим образом:

// n is the number of elements in the given sequence
p = all permutations of [0, 1, ..., n - 1] in lexicographical order    
for permutation in p:  
        for i = 0 ... n - 1
            print(s[permutation[i]]) // s is the given sequence

Вы можете сгенерировать все перестановки [0, 1, ..., n - 1], используя любой стандартный алгоритм (рекурсивно или начиная с {0, 1, ..., n - 1} и генерируя следующую перестановку n! - 1 раз). На самом деле стандартный рекурсивный алгоритм генерации всех перестановок, применяемый непосредственно к данной последовательности, будет генерировать их в правильном порядке (и не требует сравнения элементов).

Вот псевдокод рекурсивного алгоритма:

// Generates all permutations recursively
// permutation - a prefix of an arbitrary permutation
// sequence - the input sequence
// used - a boolean array where used[i] = true if and only if
// an element with index i is already in permutation
def generatePermutations(permutation, sequence, used)
    if permutation.length() == sequence.length()
        // The permutation is fully generated
        print(permutation)
    else
        // Adds all elements that are not present in permutation yet.
        // Starts with the smallest index to maintain the correct order.
        for i = 0 ... sequence.length() - 1
            if not used[i]
                used[i] = true
                permutation.push_back(sequence[i])
                generatePermutations(permutation, sequence, used)
                used[i] = false
                permutation.pop_back()

sequence = input()
permutation = an empty list
used = array of sequence.length() elements filled with a
generatePermutations(permutation, sequence, used)
person kraskevich    schedule 11.01.2015
comment
Вы уверены, что это будет правильный порядок? Как здесь: geeksforgeeks. org/ последние 2 элемента не по порядку. - person maciek; 12.01.2015
comment
@maciek Когда я упомянул стандартный рекурсивный алгоритм, я имел в виду что-то вроде: для всех чисел, которые еще не добавлены, добавьте его конец и продолжайте рекурсивно, а не алгоритм в ссылке, которую вы разместили. - person kraskevich; 12.01.2015
comment
Это именно то, что я ищу - каков алгоритм рекурсивной генерации {0...n-1} без сравнения элементов. Основная идея моего вопроса заключается в этом стандартном алгоритме. Мне не нужны ярлыки, такие как перестановка чисел и печать соответствующих строк. - person maciek; 12.01.2015
comment
@maciek Я добавил псевдокод для рекурсивной генерации. - person kraskevich; 12.01.2015
comment
Спасибо @ILoveCoding, я переписал это на Python, и это сработало :) Теперь я должен понять: почему? - person maciek; 13.01.2015