生成子序列

我有一个类似“0189”的字符串，为此我需要生成所有的子序列，但是必须保留单个字符的顺序，即这里9不应该在0,1或8之前出现。例： 0,018,01,09,0189,18,19,019等生成子序列

另一个例子是“10292”，其子序列为：1,10,02,02,09,29,92等等正如你可能注意到'02'两次，因为'2'在给定的字符串中出现了两次。但是，像21：01,91那样的事情是无效的，因为要维持秩序。

任何算法或伪代码，可以在C/C++中实现，将不胜感激！

来源

2012-08-02 kunal18

应该是：C还是C++？ – 2012-08-02 08:57:16

每当有人说“C/C++”时，一只小猫就会死亡。 – Philip 2012-08-02 08:57:41

因为他要求算法或伪代码'C/C++'意味着C或C++是足够合理的。 – john 2012-08-02 08:58:39

我推荐使用的序列的power set和该组二进制数的从0到2^n - 1，其中n之间的自然对应关系为所述序列的长度。

在你的情况下，n是4，所以考虑0 = 0000 .. 15 = 1111;在二进制表达式中有一个1包含序列中的相应项目。为了实现这一点，你需要位位移和二进制操作：

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); 
}

还要考虑你会如何处理不是可以通过int覆盖更长的序列（提示：考虑溢出和算术进位）。

来源

2012-08-02 09:02:26 ecatmur

+1因为你击败了我 – 2012-08-02 09:08:07

这将产生所有子序列。如果需要生成子序列UPTO特定长度（例如，4 =>长度为4,3,2,1的子序列），该怎么办？ – kunal18 2012-08-03 20:50:14

在这种情况下，递归（或基于递归的）解决方案将是适当的。 – ecatmur 2012-08-05 20:03:35

尝试递归方法：

该组子序列可以被分成包含第一字符的那些和那些不包含它
含有的第一个字符的那些被通过附加该字符建立在子序列不包含它（+仅包含第一个字符本身子）

来源

2012-08-02 09:04:45

__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']

来源

2012-08-02 13:42:31

在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]:

来源

2012-08-04 08:24:06 Paddy3118

回答

相关问题