Xpoint
   [напомнить пароль]

Алгоритм сочетаний соседних терминов

Метки: [без меток]
2012-01-19 21:30:32 [обр] OlgaV[досье]

Допустим, задана последовательность терминов: ab cd xy za с максимальным числом терминов в комбинации 3.
требуется получить следующие комбинации:

abcdxy za
ab cdxyza
abcd xyza
ab cdyx za
abcd xy za
ab cd xyza
ab cd xy za

Заранее спасибо!

спустя 4 часа 12 минут [обр] Евгений Седов aka KPbIC(0/176)[досье]
Количество элементов в последовательности может быть произвольным?
спустя 20 минут [обр] OlgaV[досье]
Да, количество элементов в исходной посделовательности, а также максимальное число терминов может быть произвольным.
количество терминов в исходной последовательности N (N>=1, в примере N=4), максиматьное число терминов в комбинации 1-M (M>=1, в примере M=3)
спустя 22 минуты [обр] Thirteensmay(0/157)[досье]

Возможно сильно не оптимально, но если др. варианта не найдете:

  1. Создаем словарь (справочник) терминов, т.е. нумерованный список:
1 -  ab; 2 - cd; 3 - xy; 4 - za

Далее считаем что дана последовательность терминов: 1 2 3 4

  1. Строим матрицу комбинаций каждого термина, с учетом максимального числа терминов в комбинации, в данном случае 3, путем последовательного сканирования исходного набора и наполнения матрицы построчно (каждый термин - отдельная строка):
1 1c2 1c2c3
2 2c3 2c3c4
3 3c4
4
  1. Вычисляем результирующие комбинации путем прохода по элементам матрицы, начиная с первого доступного, продолжая доступным в следующей относительно последнего термина текущего элемента строке. Задействованные в пределах начальной комбинации расчета элементы полностью просчитанных цепочек помечаем как недоступные, при переключении на следующую начальную комбинацию метки недоступности сбрасываем.

Т.е. следующим образом: начинаем с 1, вычисляем что этот элемент оканчивается термином 1, значит следующий элемент смотрим в строке 2, там есть более одного доступного элемента поэтому элемент 1 пока не помечаем, переключаемся на элемент 2, далее аналогично на 3, далее доступный элемент 4 только один поэтому элемент 3 помечаем и имеем первую результирующую цепочку - 1 2 3 4, также имеем в матрице помеченным как недоступный элемент 3.

На следующей итерации таким образом выбираем цепочку 1 2 3c4 и помечаем элемент 2. Далее имеем цепочку 1 2c3 4 и помеченный 2c3, далее имеем 1 2c3c4 и помеченный 1, т.е. начальную комбинацию 1 мы полностью просчитали и теперь переключаемся на 1c2, сбрасываем метки. Для 1c2 имеем цепочки 1c2 3 4 и 1c2 3c4, для начальной комбинации 1c2c3 имеем одну цепочку - 1c2c3 4. Т.е. в результате имеем искомые цепочки:

1 2 3 4,
1 2 3c4,
1 2c3 4,
1 2c3c4,
1c2 3 4,
1c2 3c4,
1c2c3 4.
спустя 19 минут [обр] Thirteensmay(0/157)[досье]
По идее вместо матрицы можно сделать динамический массив для меток, а все остальное вычислять исходя из словаря, память жрать не будет, но по процессору напряжнее.
спустя 9 минут [обр] OlgaV[досье]
Спасибо Thirteensmay!
Powered by POEM™ Engine Copyright © 2002-2005