Как получить все комбинации подпоследовательности Строки (в Java или C++ и т.д.)

В C ++ задана следующая процедура:

template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Mark Nelson http://marknelson.us */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator i1 = first;
   Iterator i2 = last;
   ++i1;
   if (last == i1)
      return false;
   i1 = last;
   --i1;
   i1 = k;
   --i2;
   while (first != i1)
   {
      if (*--i1 < *i2)
      {
         Iterator j = k;
         while (!(*i1 < *j)) ++j;
         std::iter_swap(i1,j);
         ++i1;
         ++j;
         i2 = k;
         std::rotate(i1,j,last);
         while (last != j)
         {
            ++j;
            ++i2;
         }
         std::rotate(k,i2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

Затем вы можете выполнить следующее:

std::string s = "12345";
for(std::size_t i = 1; i <= s.size(); ++i)
{
   do
   {
      std::cout << std::string(s.begin(),s.begin() + i) << std::endl;
   }
   while(next_combination(s.begin(),s.begin() + i,s.end()));
}

Простейший алгоритм создания подмножеств набора размера N состоит в том, чтобы рассматривать все двоичные числа с использованием N битов. Каждая позиция в номере представляет собой элемент из набора. Если бит в числе равен 1, соответствующий элемент набора находится в подмножестве, в противном случае этот элемент не входит в подмножество. Поскольку биты в числе упорядочены, это сохраняет порядок исходного набора.

Ссылки:

1. « Эффективное перечисление подмножеств набора »; Loughry, Hemert and Schoofs
2. « Создание подмножеств »; Репозиторий алгоритмов Stony Brook

используя python, модуль itertools определяет метод комбинаций (), который делает именно то, что вам нужно.

from itertools import *
list(combinations( '12345', 2 ))

даст вам:

[('1', '2'), ('1', '3'), ('1', '4'), ('1', '5'), ('2', '3'), ('2', '4'), ('2', '5'), ('3', '4'), ('3', '5'), ('4', '5')]

Для этого вы можете использовать следующий класс (в Java):

class Combinations {

  String input;
  StringBuilder cur;

  private void next(int pos, int reminder) {
    cur.append(input.charAt(pos));

    if (reminder == 1) {
      System.out.println(cur);
    } else {
      for (int i = pos + 1; i + reminder - 1 <= input.length(); i++)
        next(i, reminder - 1);
    }
    cur.deleteCharAt(cur.length() - 1);
  }

  public void generate(String input) {
    cur = new StringBuilder();
    this.input = input;
    for (int length = 1; length <= input.length(); length++)
      for (int pos = 0; pos + length <= input.length(); pos++)
        next(pos, length);
  }
}

Для запуска вашего примера используйте следующий код:

new Combinations().generate("12345");

Порядок вывода такой же, как в примере. Не требуется хранить все подмножества, а затем сортировать их для получения описанного вами порядка.

Адриан Плиссон s answer показывает, как в Python извлекаются все подпоследовательности указанной длины (для произвольных типов данных последовательности). OP указывает, что он работает со строками и хочет всех подпоследовательностей. Таким образом, используя itertools.combinations , мы определяем:

>>> from itertools import combinations
>>> def subseq_combos(inp):
...     return (''.join(s) for r in range(len(inp) + 1) for s in combinations(inp, r))
... 
>>> list(subseq_combos('12345'))
['', '1', '2', '3', '4', '5', '12', '13', '14', '15', '23', '24', '25', '34', '35', '45', '123', '124', '125', '134', '135', '145', '234', '235', '245', '345', '1234', '1235', '1245', '1345', '2345', '12345']

(Если пустая подпоследовательность должна быть опущена, используйте range (1, len (inp) + 1)) .)

Когда вы разветвляете процесс, вы в основном получаете две (почти) точные копии процесса, и обе они продолжат работу.

Итак, что происходит. заключается в том, что сами дочерние элементы продолжают цикл в собственном пространстве процесса (после того, как они распечатывают свой вывод) , а также , как и родительский процесс. И, фактически, поскольку эти дети тоже разветвляются, внуки также будут продолжать жить с этого момента. Я уверен, что есть формула для определения того, сколько детей у вас в итоге будет (вероятно, что-то вроде N!), Но в данный момент у меня нет сил, чтобы это выяснить. Лучше использовать следующее решение.

Способ отличить родительский от дочернего - это возвращаемое значение из fork .

• Если вы получите -1, вы '