Générer des sous-séquences

Question

J'ai une chaîne comme "0189", pour laquelle j'ai besoin de générer toutes les sous-séquences, mais l'ordre des caractères individuels doit être conservé, c'est-à-dire 9 ne doit pas précéder 0, 1 ou 8. 0, 018, 01, 09, 0189, 18, 19, 019, etc.

Un autre exemple est "10292" pour lequel les sous-séquences seraient: 1, 10, 02, 02, 09, 29, 92, etc. Vous avez peut-être remarqué '02' deux fois, puisque '2' vient deux fois dans la chaîne donnée. Mais encore une fois des choses comme: 21, 01, 91 sont invalides car la commande doit être maintenue.

Tout algorithme ou code psuedo, qui pourrait être implémenté en C/C++ serait apprécié!

Answer 1

Je vous recommande d'utiliser la correspondance naturelle entre le power set d'une séquence et l'ensemble des nombres binaires 0-2^n - 1, où n est la longueur de la séquence.

Dans votre cas, n est 4, alors considérez 0 = 0000 .. 15 = 1111; où il y a un 1 dans l'expression binaire inclure l'élément correspondant de la séquence. Pour mettre en œuvre ce que vous aurez besoin bitshift et opérations binaires:

for (int i = 0; i < (1 << n); ++i) { 
    std::string item; 
    for (j = 0; j < n; ++j) { 
     if (i & (1 << j)) { 
      item += sequence[j]; 
     } 
    } 
    result.push_back(item); 
} 

Voir également comment vous gérer des séquences plus longues que ce qui peut être couvert par un int (indice: considérer le débordement et l'arithmétique carry).

Answer 2

Essayez une approche récursive:

• l'ensemble des séquences peut être divisé en ceux contenant le premier caractère et ceux ne contenant pas qu'il
• ceux contenant le premier caractère sont construits en ajoutant ce caractère les séquences qui ne contiennent pas (+ qui contient la sous-séquence seul le premier caractère lui-même)

Answer 3

__author__ = 'Robert' 
from itertools import combinations 

g = combinations(range(4), r=2) 
print(list(g)) #[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] 

def solve(string_): 
    n = len(string_) 
    for repeat in range(1, len(string_) + 1): 
     combos = combinations(range(len(string_)), r=repeat) 
     for combo in combos: 
      sub_string = "".join(string_[i] for i in combo) 
      yield sub_string 

print(list(solve('0189'))) #['0', '1', '8', '9', '01', '08', '09', '18', '19', '89', '018', '019', '089', '189'] 


#using recursion 

def solve2(string_, i): 
    if i >= len(string_): 
     return [""] #no sub_strings beyond length of string_ 
    character_i = string_[i] 
    all_sub_strings = solve2(string_, i + 1) 
    all_sub_strings += [character_i + sub_string for sub_string in all_sub_strings] 
    return all_sub_strings 


print(solve2('0189', 0)) #['', '9', '8', '89', '1', '19', '18', '189', '0', '09', '08', '089', '01', '019', '018', '0189'] 

Answer 4

En Python:

In [29]: def subseq(s): return ' '.join((' '.join(''.join(x) for x in combs(s,n)) for n in range(1, len(s)+1))) 

In [30]: subseq("0189") 
Out[30]: '0 1 8 9 01 08 09 18 19 89 018 019 089 189 0189' 

In [31]: subseq("10292") 
Out[31]: '1 0 2 9 2 10 12 19 12 02 09 02 29 22 92 102 109 102 129 122 192 029 022 092 292 1029 1022 1092 1292 0292 10292' 

In [32]: