Создать последовательность без перестановок

Question

Я использую две цифры в целых числах для представления одного элемента. То есть 3345512 представляет четыре элемента: [3,34,55,12]. Затем я неоднократно добавляю одно к целому, чтобы получить другую последовательность элементов. При создании таких последовательностей я получаю перестановки одной и той же последовательности, то есть 3341255 = [3,34,12,55], что в моем случае эквивалентно числу 3345512 = [3,34,55,12]. Поэтому я хотел бы избежать перестановок последовательности, с которой я уже сталкивался. Я не хочу хранить цифры по мере их роста (10^30 и более). Я попытался использовать фильтр цветения, но он не смог обработать количество элементов. Существует ли тривиальное решение для генерации последовательностей без перестановок?

[EDIT] Вот крошечный скрипт python, который должен работать. Ради лучшей понятности я использую одну цифру с if s[idx] == 9: вместо if s[idx] == 99: Если у вас есть более простое решение, я буду принимать его в качестве ответа.

import time 
s = [1] 
while True: 
    idx = 0 
    while not idx+1 == len(s) and not s[idx] < s[idx+1]: 
     s[idx] = 1 
     idx += 1 
    if s[idx] == 9: 
     s[idx] = 1 
     s.append(1) 
    else: 
     s[idx] += 1 
    print repr(s) 
    time.sleep(0.7) 

Answer 1

То, о чем вы просите, это комбинации, а не перестановки. Похоже, вы пытаетесь получить уникальные комбинации из 4 элементов из списка из 100. То есть ваши возможные значения: 00 - 99.

Вы могли бы генерировать все комбинации с вложенным циклом, как это:

for (i = 0 to 96) 
    for (j = i + 1 to 97) 
     for (k = j + 1 to 98) 
      for (l = k + 1 to 99) 
       write i, j, k, l 

Это гарантирует, что вы не получите ту же самую комбинацию.

Вы также отметить, что в сгенерированных комбинациях:

i < j < k < l 

Если вы сделаете ваши последовательности всегда удовлетворяют, что неравенство, то вы не получите дубликат комбинации.

Так что ваш пример 3345512 никогда не будет сгенерирован. Это будет 3123455.

Учитывая, что при добавлении от 3123499, вы не заходите в 3123500, а скорее в 3123536. В принципе, если вы переполняете одну позицию, вы увеличиваете следующую позицию, а исходное положение становится (следующая позиция + 1). Таким образом, 3999999 увеличивается до 4050607.

Очевидно, вы не можете сделать это с помощью простого целочисленного приращения. Я бы предложил использовать 4-байтовое значение и немного логики.

Вот еще один способ сделать это.

Представьте, что ваш алфавит - всего 4 символа, [0, 1, 2, 3]. В общей сложности существует 16 возможных уникальных комбинаций. Вам нужны уникальные комбинации из двух предметов.

Теперь рассмотрим 4-битное число, которое может содержать значения от 0 до 15. Вы можете сопоставить это число с уникальными комбинациями, чтобы число 3 (0011 двоичное) соответствовало комбинации 0, 1. То есть, бит 0 установлен, и бит 1 установлен. Должно быть ясно, что число с 2 битами соответствует уникальной комбинации из двух символов. В случае наших 2-х комбинаций в алфавите 4 пунктов, мы имеем:

0, 1 (0011) 
0, 2 (0101) 
0, 3 (1001) 
1, 2 (0110) 
1, 3 (1010) 
2, 3 (1100) 

При этом, вы можете увеличивать целое, увидеть, если он установлен на два бита, а затем перевести из набора битов символов в вашем алфавите.

Вы можете сделать то же самое с выбором 4-комбинации из набора из 100 символов. Работа со 100-битным числом немного сложна, но не невозможна. Поскольку вы просто увеличиваете, вы можете сделать это с помощью пары 64-битных чисел.

Определение того, сколько бит установлено, легко сделать наивным способом. На странице Bit Twiddling Hacks показаны несколько более быстрых способов.

Существует несколько способов решения этой проблемы, все из которых можно параметризовать, чтобы выбрать уникальные k-комбинации из списка из n элементов.

Answer 2

Чтобы проверить, если данная последовательность уже сгенерирована и может быть пропущена, вы должны генерировать «предыдущую» перестановку текущей последовательности, которая будет сгенерирована, если считать от нуля, и сравнить его с исходным номером ,

Вы можете найти эту перестановку следующим образом:

Если числа в порядке возрастания - например, [3] [4] [5] [6] - вы можете остановиться, так как не меньше, перестановка этих чисел.

Если последовательность имеет некоторую не увеличивающуюся часть - например, [3] [5] [4] [8] [6] [7] [8] [9]. Эта последовательность имеет две не увеличивающиеся части. 5-4 и 8-6.

Найдите последний номер, который больше, чем его преемник. Это первый 8.

[3] [5] [4] [8] [6] [7] [8] [9]

Найти наибольшее количество позади 8, что на самом деле меньше, , Это 7.

[3] [5] [4] [8] [6] [7] [8] [9]

Move 7 в положение 8, и оставить все другие номера в порядке убывания.

[3] [5] [4] [7] [9] [8] [8] [6]

Теперь, если эта последовательность меньше исходного числа - вы знаете, что это было еще не сгенерирован. В противном случае вы можете пропустить его.