Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Інші мови програмування → Програма для генерування всіх перестановок елементів мультимножини
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
Шановні форумчани, прошу порадити де можна почитати про алгоритми генерування всіх перестановок елементів мультимножини.
(!перестановок) - спiвпадаючi.
Велике Вам спасибі
Для того, щоб дізнатися, що з "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---]. Якщо попередньої мапи не існує (тобто ми перенесли на початок все у всіх мапах), перебір закінчено.
У 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 до кінця(перепрошую за генераторну функцію з рекурсією, але це найшвидший спосіб написати щось подібне).
Питання було про мультимножини. Тобто 'aab' -> 'aab', 'aba', 'baa'.
Питання було про мультимножини. Тобто 'aab' -> 'aab', 'aba', 'baa'.
Тоді робимо set(permutations('aab')), щоб виключити дублікати.
set(it.permutations('aaaaaaaaaaaaaa'))скільки часу на вашій машині обчислюватиметься?
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Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися