Создание уникальных комбинаций из списка возможных повторяющихся символов

Я ищу для создания комбинаций из списка элементов. Прямо сейчас я использую подход генерации набора мощности. Например, чтобы сгенерировать комбинации из {a,b,c}, я перечислю 001,010,100,101 и т. д. и возьму элемент, для которого соответствующий двоичный индекс установлен на 1. Но проблема возникает, когда в строке есть повторяющиеся символы. список Произнесите {a,a,b}. вышеприведенный подход даст a,a,b,ab,ba,aab. где, как я хотел бы видеть только a,b,ab,aa,aab.

Я думал написать какую-нибудь двоичную маску для устранения повторяющихся строк, но не смог. Любые мысли о том, как генерировать уникальные комбинации?


combinations combinatorics
person Community    schedule 04.10.2010    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вместо того, чтобы генерировать битовые векторы, вы можете генерировать векторы положительных целых чисел длины, равной количеству различных элементов, при условии, что каждый компонент может принимать значения от 0 до кратности соответствующего элемента. В приведенном выше примере есть два различных элемента (a и b) с кратностью 2 и 1 соответственно. Следовательно, вы получите

a b
-------
0 1 --> b
1 0 --> a
1 1 --> ab
2 0 --> aa
2 1 --> aab
person Philip Starhill    schedule 04.10.2010
comment
Спасибо за мысль. пытаюсь реализовать. Сначала я найду уникальный чартерный набор и перечислю возможные двоичные строки. Затем для каждой двоичной строки я вычислю возможные повторяющиеся строки символов на основе отсутствия повторения. Итак, моей проблеме теперь задана строка, подобная ab, с количеством повторений a = 2 и количеством повторений b = 2, мне нужно сгенерировать ab, aab, aabb, abb. Любые мысли о том, как создать это. - person ; 05.10.2010
comment
@james Я думаю, это будет зависеть от деталей используемого вами языка программирования и требований проблемы. Например, вам нужно иметь в памяти сразу все эти комбинации? Вам нужно только распечатать их на экране? Должны ли они быть строками в смысле C или они могут быть чем-то более абстрактным? Я бы предложил либо отредактировать исходный вопрос с этой дополнительной информацией, либо задать новый вопрос, если вы считаете, что эти проблемы достаточно отделены от исходного сообщения. - person Philip Starhill; 05.10.2010