在保持原始订单的同时,从数字字符串中查找所有可能的数字组合

Question

假如你有字符串:1234

我需要的是从这个字符串生成所有可能的数字组合,但必须保持字符串的原始顺序.

每个结果中必须至少有2个数字.

在1234的情况下,输出将是列表的列表

输出清单:

list: 1, 2, 3, 4
list: 12, 3, 4
list: 123, 4        --Note a list containing only 1234 is not valid
list: 1, 23, 4
list: 1, 234
list: 1, 2, 34
list: 12, 34

另请注意,每个结果列表中的数字始终与原始字符串1234的顺序相同.因此,组合34,21或213,4的列表无效.

我能想到的唯一方法:

1. 从第一个索引开始(1)
2. 附加下一个数字以形成一个新数字(12)
3. 然后以递归方式传递新形成的数字以附加下一个数字(123)
4. 第一个索引完成后,我们用第二个索引重新开始(2)
5. ...

然而,根据我的方法,我不知道如何生成12,34组合

任何帮助是极大的赞赏!

Answer 1

1 | 2 | 3 | 4 | 5
  |   |   |   |
  d1  d2  d3  d4

假设原始字符串的长度为5,我们通过添加一个可以为空的分隔符d1,d2,d3和d4来划分该字符串.

• 当D1,D2,D3,D4是全空的,我们得到的12345.
• 当d2,d3,d4为空时,我们得到 1, 2345
• 当d1,d2,d3,d4都不为空时,我们得到了1,2,3,4,5

对于我们添加的每个分隔符,它有两个选项:可见或消失,因此总可能的数量是2^(n-1) - 1当n是原始字符串的长度时

然后,我们将解决的下一个问题是迭代所有可能性:使用二进制值来表示分隔符:

for (int i = 1; i <= pow(2, n - 1); i++) {
     // i = 1, 0b0001, d4 is visible, we get 1234,5
     // i = 2, 0b0010, d3 is visible, we get 123,45
     // i = 3, 0b0011, d3 and d4 is visible, we get 123,4,5
     // i = 4, 0b0100, d2 is visible, we get 12,345
     // i = 5, 0b0101, d2 and d4 is visible, we get 12, 34, 5
     // i = 6, 0b0110, d2 and d3 is visible, we get 12, 3, 45
     // i = 7, 0b0111, d2,d3,d4 is visible, we get 12,3,4,5
     // go on...
}

希望有帮助......