Алгоритм для поиска последовательности подпоследовательностей

Question

Последовательность [1,2,3] рассмотрим. Эта последовательность имеет следующие 6 различных последовательностей: [1] и [2] и [3] и [1,2] и [2,3] и [1,2,3]

Примечание! Длина начальной последовательности может составлять до 100 цифр. Пожалуйста, помогите мне. Как я могу сделать следующие последовательности? Мне нравится больше изучать подобные алгоритмы. Скажите, пожалуйста, имя этого типа алгоритмов.

Answer 1

Здесь приведен код c для печати всех подпоследовательностей. Алгоритм использует вложенные циклы.

#include<stdio.h> 

    void seq_print(int A[],int n) 
{ 
    int k; 
    for(int i =0;i<=n-1;i++) 
    { 
     for(int j=0;j<=i;j++) 
     { 
      k=j; 
      while(k<=i) 
      { 
       printf("%d",A[k]); 
       k++; 

      } 
      printf("\n"); 
     } 
} 

} 

void main() 
{ 
    int A[]={1,2,3,4,5,6,7,8,9,0}; 
    int n=10; 
    seq_print(A,n); 

} 

Answer 2

Ваша проблема может быть сведена к ошибке Combination. В stackoverflow уже существует множество решений. Вы можете проверить this, это может быть полезно для вас.

Answer 3

Это называется a power set (в вашем случае пустой комплект исключается).

Чтобы создать комплект питания, начните с набора с пустым набором в нем; затем для каждого элемента на входе установлен расширить возможности установки со всеми его подмножеств накопленных до сих пор с текущим элементом включен (в Python):

def powerset(lst): 
    S = [[]] 
    for item in lst: 
     S += [subset + [item] for subset in S] 
    return S 

Пример:

print(powerset([1, 2, 3])) 
# -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] 

К избегать одновременного создания всех подмножеств, может быть использовано рекурсивное определение:

• источник питания пустого Набор представляет собой набор с пустым множеством в нем
• власти набор из набора с n элементами содержат все подмножества из власти установить набор с n - 1 элементами плюс все эти подмножества с n -й вошедшими.

def ipowerset(lst): 
    if not lst: # empty list 
     yield [] 
    else: 
     item, *rest = lst 
     for subset in ipowerset(rest): 
      yield subset 
      yield [item] + subset 

Пример:

print(list(ipowerset([1, 2, 3]))) 
# -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] 

Еще один способ создания набора мощности заключается в создании r -длина подпоследовательности (комбинация) для всех r от нуля до размера входного набора (itertools recipe):)

from itertools import chain, combinations 

def powerset_comb(iterable): 
    s = list(iterable) 
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) 

Пример:

print(list(powerset_comb([1, 2, 3]))) 
# -> [(), (1,), (2,), (3,), (1,2), (1,3), (2,3), (1,2,3)] 

Смотрите также what's a good way to combinate through a set?.