字符串可能的组合

假设一个由四个符号组成的字符串，例如s = abcd 仅考虑那些每个符号只有一个实例的字符串，这样s = bacd和s = dacb都是有效字符串，但s = aabc不是。这给了4！可能的组合。字符串可能的组合

现在，每个符号可以采取的值之间

a = [0, 1] 
b = [0, 1, 2, 3] 
c = [0, 1] 
d = [0, 1, 2]

因此我最终可能有s=cdab=0112或s=abcd=0000或s=abdc=1320等。

我希望计算多少组合（无重复）可以串取。

我写了一个算法，探测所有不同的组合和丢弃重复，但我想了解，如果可以构造一个公式可以退回相同的结果（不是所有有效的组合列表，但只有它们的数量）。

谢谢

来源

2012-08-04 Flavio

如果你把一个横向步长，根据你的榜样

你的成员是A0，A1，B0，B1，B2，B3 ...... D2，这意味着可能的组合是11 ！

来源

2012-08-04 14:55:08

不，这不是因为4. – Flavio 2012-08-04 19:59:55

该死的看错了问题... – 2012-08-05 11:35:02

不，它不是11！无论是。让我举一个例子。如果我有3个符号a = [0] b = [0,1] c = [0,1,2]和s = abc，则s的可能组合是（000,001,002,010,011,012）。对于s = acb，你有（000,001,010,011,020,021）等等。您丢弃重复项（在本例中）剩下16种组合（000,001,002,010,011,012,020,021,100,101,102,110,120,200,201,210）。我发现了一个运行在O（n！）中的算法（在这个例子中是3！），但是我想知道O（n）还是O（1）是可行的。 – Flavio 2012-08-05 13:10:24

字符串可能的组合

回答

相关问题