Нужна помощь в решении следующей задачи. Есть некоторое количество массивов, их нужно объединить в один и сгенерировать перестановки получившегося массива, но с сохранением "относительного" порядка.
Пример: пусть у нас есть два массива: [a,b,c] и [d,e]. Объединив их мы получим [a,b,c,d,e]. Его перестановка [a,d,b,e,c] подходит т.к. в ней сохраняется "относительный" порядок (b идёт позже a, с идёт позже b и e идёт после d). Другая перестановка например [a,c,d,e,b] не подходит.
Вопрос как сгенерировать все такие перестановки?
Здравствуйте, av239, Вы писали:
A>Нужна помощь в решении следующей задачи. Есть некоторое количество массивов, их нужно объединить в один и сгенерировать перестановки получившегося массива, но с сохранением "относительного" порядка.
A>Пример: пусть у нас есть два массива: [a,b,c] и [d,e]. Объединив их мы получим [a,b,c,d,e]. Его перестановка [a,d,b,e,c] подходит т.к. в ней сохраняется "относительный" порядок (b идёт позже a, с идёт позже b и e идёт после d). Другая перестановка например [a,c,d,e,b] не подходит.
A>Вопрос как сгенерировать все такие перестановки?
Пусть массивы a1..am, длина l1..lm.
Идея.
Поставим первый массив a1. Определим позицию a2[0] от 0-й (перед a1[0]) до конца (после a1[l1-1]). Определим позицию a2[1] от позиции a2[0] до конца. И т.д. Потом в полученном массиве длины l1+l2 таким же образом расставляем a3. И т.д.
Реализация в стиле next_permutation.
Начальная позиция такая: am[0]...am[lm-1]a(m-1)[0]...a2[l2-1]a1[0]..a1[l1-1]. Ищем элемент am[lm-1]. Если он не последний то сдвигаем его вправо и все. Если он последний, то, начиная с предыдущего элемента, ищем элемент am[lm-2]. Если он не последний (перед am[lm-1]), то сдвигаем его, и ставим am[lm-1] в ту же позицию. Если же он последний, то ищем am[lm-3]. И т.д. Найдя am[i] такой, что после него элемент не из am, мы его сдвигаем, а все старшие элементы передвигаем с конца в его позицию. Если же все элементы am стоят последними, то сдвигаем весь массив am в начало, и ищем в обратном порядке элемент a(m-1) такой, что после него элемент не из a(m-1). Если такого опять нет, то сдвигаем a(m-1) в начало, но после am, и работаем с a(m-2). И т.д. Если таким образом в поиске элемента мы дошли до a1, то все, выходим, т.к. мы воссоздали изначальную расстановку.
В твоем примере: [x1,x2,x3] [y1,y2]
y1 y2 x1 x2 x3
y1 x1 y2 x2 x3
y1 x1 x2 y2 x3
y1 x1 x2 x3 y2
x1 y1 y2 x2 x3
x1 y1 x2 y2 x3
x1 y1 x2 x3 y2
x1 x2 y1 y2 x3
x1 x2 y1 x3 y2
x1 x2 x3 y1 y2
(потом снова y1 y2 x1 x2 x3)
Реализация а-ля Кнут (может быть поэффективней, то больше кода писать, и надо быть более аккуратным).
Начальная позиция такая же. Будем считать, что элементы ai[k] < aj[k'] <=> i < j. Т.е. элементы одного массива эквиваленты. Пусть у нас теперь есть некоторая (правильная) расстановка s[0]..s[l1+...+lm-1]. С конца ищем первую пару такую, что s[j] > s[j+1]. Теперь вправо от s[j] ищем последний элемент s[i'] такой, что он меньше s[j] (им может оказаться как s[j+1], так и какой-то последующий элемент). Теперь влево от s[i'] надо найти первый элемент s[i] из массива с тем же номером, что и s[i']. Теперь делаем так: s[i] идет в позицию j, все элементы от s[i+1] до s[i'] сдвигаются влево на один, а s[j] идет на место s[i']. Теперь весь хвост вправо от позиции j, в которой теперь s[i], упорядочен по возрастанию (причем возрастание не строгое). Нам надо хвост развернуть по убыванию, но при этом сохранить порядок равных элементов (т.е. элементов из одного массива). Тут повсюду тонкости реализации, особенно эффективной реализации. Если поищещшь на рсдн, найдешь конкретные реализации, я даже помню, я писал как-то.
В твоем примере: [x1,x2,x3] [y1,y2]
(если i=i', я пишу только i)
y1 y2 x1 x2 x3
j i i'
y1 x1 y2 x2 x3
j i i'
y1 x1 x2 y2 x3
j i
y1 x1 x2 x3 y2
j i i'
x1 y1 y2 x2 x3
j i i'
x1 y1 x2 y2 x3
j i
x1 y1 x2 x3 y2
j i i'
x1 x2 y1 y2 x3
j i
x1 x2 y1 x3 y2
j i
x1 x2 x3 y1 y2
(j == -1 -> return)
Здравствуйте, av239, Вы писали:
A>Нужна помощь в решении следующей задачи...
Эта задача уже всплывала здесь —
http://rsdn.ru/forum/alg/3571307.flat.aspxАвтор: Рысцов Денис
Дата: 16.10.09
=)
Здравствуйте, Рысцов Денис, Вы писали:
РД>Здравствуйте, av239, Вы писали:
A>>Нужна помощь в решении следующей задачи...
РД>Эта задача уже всплывала здесь — http://rsdn.ru/forum/alg/3571307.flat.aspxАвтор: Рысцов Денис
Дата: 16.10.09
=)
Там более общая задача.
