1

Тема: Програма для генерування всіх перестановок елементів мультимножини

Шановні форумчани, прошу порадити де можна почитати про алгоритми генерування всіх перестановок елементів мультимножини.

2

Re: Програма для генерування всіх перестановок елементів мультимножини

(!перестановок) - спiвпадаючi.

анаграм

Білоруський журнал «Радиолюбитель»
Lead Radar systems engineer & Software developer of industrial automation
Мої розробки та відеоблог

3

Re: Програма для генерування всіх перестановок елементів мультимножини

Велике Вам спасибі

4 Востаннє редагувалося koala (29.10.2016 14:49:09)

Re: Програма для генерування всіх перестановок елементів мультимножини

Для того, щоб дізнатися, що з "AAAAAA" можна зробити 1 перестановку, генерувати 720 і перевіряти їх на збіг? Оригінальне рішення, але для довгих перестановок явно не годиться.

Я б робив так:
1. Множину переробляємо на словник (dict, map - залежно від мови) {елемент: кількість}. Наприклад, "aaabbc" ->{a:3,b:2,c:1} (позначимо цей словник d). Бажано відсортувати його за кількістю, але не обов'язково.
2. Для кожного елементу словника складаємо мапу розташування елементів серед комірок: для першого елементу - серед усіх, для другого - серед кількості, зменшеної на кількість перших елементів і т.д. Наприклад,
a -> [aaa---] (6 комірок, d[ a ]=3 зайняті)
b -> [bb-] (3=6-d[ a ] комірки, d[ b ]=2 зайняті)
c -> [c] (1=6-d[ a ]-d[ b ] комірка, d[ c ]=1 зайнята)
3. З цієї структури можна отримати i-й елемент перестановки: якщо в першій мапі i-а комірка зайнята, повертаємо перший елемент; якщо вільна - лічимо кількість m елементів лівіше від неї і запитуємо i-m-й елемент 2-ї таблиці і т.д.
4. Коли треба отримати наступну перестановку - намагаємося в останній мапі отримати наступний стан:
- якщо найправіша зайнята комірка - не остання, просто зсуваємо її правіше: [aa-a--] -> [aa--a-]
- якщо остання комірка зайнята, беремо весь ланцюжок знайнятих справа, пересуваємо найправішу зайняту, яку можна пересунути, і переносимо ланцюжок після неї: [-a--aa] -> [--aaa-]
- якщо пересувати нема чого, переносимо все на початок і повторюємо процедуру з попередньою мапою: [---aaa] -> [aaa---]. Якщо попередньої мапи не існує (тобто ми перенесли на початок все у всіх мапах), перебір закінчено.

Подякували: romazatorsky1

5

Re: Програма для генерування всіх перестановок елементів мультимножини

У python’і є готова функція permutations у модулі itertools.

>>> import itertools as it
>>> print('\t'.join(map(''.join, it.permutations('qwer'))))
qwer    qwre    qewr    qerw    qrwe    qrew    wqer    wqre    weqr    werq
wrqe    wreq    eqwr    eqrw    ewqr    ewrq    erqw    erwq    rqwe    rqew
rwqe    rweq    reqw    rewq

Це якщо потрібен просто результат. Якщо ж цікавить сам алгоритм, він виглядатиме приблизно так:

def permuteishenz(l, start=0):
    if start==0:
        l=list(l) # на випадок, якщо на вході не список, а послідовність якогось іншого типу
    if start>=len(l)-1:
        yield tuple(l) # додаємо поточну комбінацію до результатів
    else:
        for i in range(start, len(l)):
            yield from permuteishenz(l, start+1) # рекурсивно генеруємо перестановки хвостової частини списку
            l.append(l.pop(start)) # прокручуємо частину списку від start до кінця

(перепрошую за генераторну функцію з рекурсією, але це найшвидший спосіб написати щось подібне).

py -3 -m pip install git+https://github.com/snoack/python-goto
Подякували: romazatorsky1

6

Re: Програма для генерування всіх перестановок елементів мультимножини

Питання було про мультимножини. Тобто 'aab' -> 'aab', 'aba', 'baa'.

Подякували: romazatorsky1

7

Re: Програма для генерування всіх перестановок елементів мультимножини

koala написав:

Питання було про мультимножини. Тобто 'aab' -> 'aab', 'aba', 'baa'.

Тоді робимо set(permutations('aab')), щоб виключити дублікати.

py -3 -m pip install git+https://github.com/snoack/python-goto
Подякували: romazatorsky1

8

Re: Програма для генерування всіх перестановок елементів мультимножини

set(it.permutations('aaaaaaaaaaaaaa'))

скільки часу на вашій машині обчислюватиметься?

Подякували: romazatorsky1

9

Re: Програма для генерування всіх перестановок елементів мультимножини

koala написав:
set(it.permutations('aaaaaaaaaaaaaa'))

скільки часу на вашій машині обчислюватиметься?

Ну, тоді якось так:

def uniqperm(l):
  res=set()
  def permuteishenz(l, start=0):
    if tuple(l) in res:
        return
    if start>=len(l)-1:
        res.add(tuple(l)) # додаємо поточну комбінацію до результатів
    else:
        for i in range(start, len(l)):
            permuteishenz(l, start+1) # рекурсивно генеруємо перестановки хвостової частини списку
            l.append(l.pop(start)) # прокручуємо частину списку від start до кінця
  permuteishens(list(l))
  return res
py -3 -m pip install git+https://github.com/snoack/python-goto
Подякували: romazatorsky1