标签: combinatorics

我试图弄清楚有多少可能的方法来组合这个字符串的各种元素.

"{Hello|Hi|Hey} {world|earth}{!|.|?}"

从每个组({})中随机选择一个项目(由管道/ |分隔)并组合成一个字符串.

所以上面的"模板"可以产生:

Hello world.
Hi earth?
Hey world.
Hi world?

我猜这是一种排列,但我想确保我做对了.

如果这也适用于"n"嵌套项目,那将是非常好的.

"{{Hello|Hi|Hey} {world|earth}|{Goodbye|farewell} {noobs|n3wbz|n00blets}}"

如果可能的话,我更喜欢基于数学/统计的解决方案而不是暴力循环来获得答案.

谢谢!

我决定学习并发性,并希望了解来自两个不同进程的指令可以重叠的方式.两个进程的代码只是一个10迭代循环,在每次迭代中执行3条指令.我想出了一个问题,包括将X指令固定在一个点,然后在空间之间安装来自另一个进程的其他X指令,同时考虑到它们必须被排序(进程B的指令4必须总是在指令20之前).

我编写了一个程序来计算这个数字,查看结果我发现解决方案是n组合k,其中k是在一个过程的整个循环中执行的指令数,因此对于10次迭代,它将是30,并且n是k*2(2个过程).换句话说,n个固定的n个对象并且必须在空间中拟合n/2而没有后者n/2失去它们的顺序.

好的问题解决了.不,不是真的.我不知道为什么会这样,我明白组合的定义是,你可以用多少种方式从一组n中取k个元素,这样所有的组都是不同的,但你采用这些元素的顺序并不是'无所谓.在这种情况下,我们有n个元素,我们实际上是全部,所有指令都被执行(n C n).

如果一个人说,有2K蓝色(A)和红色(B)解释了它在一个袋子对象,你从包里取k个对象,你仍然只有k取指令时,2K指令实际执行.你能否对此有所了解？

提前致谢.

我正在寻找"排列"算法的快速实现(具有重复的排列).给定N个对象(数量a中的A,数量b中的B,......),生成所有可能的组合.
例:

Arrangement("AAA", "B", "CC") would return :   
"AAABCC" "AABACC" "AABCAC" "AABCCA" "ABAACC" "ABACAC" "ABACCA" "ABCAAC"   
"ABCACA" "ABCCAA" "BAAACC" "BAACAC" "BAACCA" "BACAAC" "BACACA" "BACCAA"   
"BCAAAC" "BCAACA" "BCACAA" "BCCAAA" "AAACBC" "AACABC" "AACBAC" "AACBCA"   
"ACAABC" "ACABAC" "ACABCA" "ACBAAC" "ACBACA" "ACBCAA" "CAAABC" "CAABAC"   
"CAABCA" "CABAAC" "CABACA" "CABCAA" "CBAAAC" "CBAACA" "CBACAA" "CBCAAA"   
"AAACCB" "AACACB" "AACCAB" "AACCBA" "ACAACB" "ACACAB" "ACACBA" "ACCAAB"   
"ACCABA" "ACCBAA" "CAAACB" "CAACAB" "CAACBA" "CACAAB" "CACABA" "CACBAA"   
"CCAAAB" "CCAABA" "CCABAA" "CCBAAA"  

(如果可能,用C,C#或Pascal编码)

在此先感谢
Philippe

也许我误解了这个问题.对于那些不熟悉Project Euler问题31的人来说,问题是:

调查英国货币面额的组合.

在英格兰,货币由英镑,英镑和便士p组成,一般流通中有八个硬币:

1p,2p,5p,10p,20p,50p,£1(100p)和£2(200p).

可以通过以下方式赚取2英镑:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

使用任意数量的硬币可以制作多少种不同的方式？

我看到这可能是一个动态编程问题,但我忍不住走捷径:

为了解决这个问题,我分解了使用1p,1p和2p以及1p,2p和5p硬币可以制造1到6便士的方法.

仅使用一分钱硬币

1. 1组合
   • 1P
2. 1组合
   • 2×1P
3. 1组合
   • 3×1P
4. 1组合
   • 4×1P
5. 1组合
   • 5×1P
6. 1组合
   • 6×1P

仅使用一便士和两便士硬币

1. 1组合
   • 1P
2. 2种组合
   • 2P
   • 2×1P
3. 2种组合
   • 2p + 1p
   • 3×1P
4. 3种组合
   • 2×2P
   • 2p + 2×1p
   • 4×1P
5. 3种组合
   • 2×2p + 1p
   • 2p + 3×1p
   • 5×1P
6. 4种组合
   • 3×2P
   • 2×2p + 2×1p
   • 2p + 4×2p
   • 6×2P

仅使用一便士,两便士和五便士硬币

1. 1种组合
   • 1P
2. 2种组合
   • 2P
   • 2×1P
3. 2种组合
   • 2p + 1p
   • 3×1P …

我有四个值

age = 23
gender = "M"
city ="Delhi"
religion = "Muslim"

我需要通过每个组合排列这些空值,如 -

23 * * *
23 M * *
23 M Delhi *
23 M Delhi Muslim
* M * *
* M Delhi *
* M Delhi Muslim
* * Delhi *
* * Delhi Muslim
* * * Muslim
* * * *

我需要在列表中按升序排列维数.因此,具有一个值的组合应该位于顶部.我有30多个属性,所以我需要一种自动化的方法在Python中执行此操作

有任何想法吗 ？

我必须实现一个问题,该问题计算来自一组n个元素的m个元素的组合和多个集合.它们的公式如下:

问题是,使用阶乘很容易溢出,所以基本上解决这个问题的解决方案是什么？

由于它是TopCoder中问题的子问题,我有以下约束:

1)程序必须用C++编写.

2)我无法加载外部库.

我想生成n个数字的排列,其中没有两个排列是彼此的反转(第一个从最后一个字符读到第一个字符与第二个字符相同).例如,n = 3,我想生成:

1 2 3 //but not 3 2 1
1 3 2 //but not 2 3 1
2 1 3 //but not 3 1 2

我不关心这两者中的哪一个会产生.该算法应适用于大n(> 20).是否有任何此类算法或方法来检查生成的排列是否是先前生成的排列的镜像？

我有一个可以说是相当大的(100种+元素)元素的列表:elements = [a, b, c, d, e, f, g...].

并且我需要建立所有可能的定向循环的列表,考虑到序列 [a,b,c,d,e], [b,c,d,e,a], [c,d,e,a,b], [d,e,a,b,c], [e,a,b,c,d]被认为是相同的,因为它们是相同定向循环的不同表示.只有起点不同.

此外,由于方向很重要,[a,b,c,d,e]并且[e,d,c,b,a]不同.

我正在寻找所有长度的定向循环,从2到len(elements).什么是最Python的方式做到这一点利用内置的优化permutations,combinations等等？

例如,我需要得到2值数组的所有组合,数字为{0,1,2},其中这两个数字不相同.我明白了

0 1
0 2
1 0
1 2
2 0 
2 1

我忽略了

0 0
1 1
2 2

现在我用

  for (int i= 0; i < L ; i++) {
                for (int j = 0; j < L; j++) {
                    if (i!= j) {

但它很慢？对此有何解决方案？L将> 4000.

我在做什么是找到分裂矩阵到4个子矩阵的每个组合

例:

 3 | 0   2  -8  -8
 5 | 3   2   2   3
 2 | 5   2   1   4
 -------------------
 3   4  -1 |  4  2
-3   6   2 |  4  3 …

这就是我的意思:

假设我们有X的颜色数和16个正方形的4×4网格,我们可以用颜色的任何与所述正方形的任何颜色.

假设您可以生成所有可能配置的列表,并且算法一个接一个地吐出(configuration#1然后configuration#2等等),有没有办法使用数字i并立即开始configuration#i？

(因为在普通硬件上无法存储1e + 16配置)

更重要的是,是否有可能得到这个算法的反转,而是给它一个配置,i为什么它将返回一个插回时将返回原始配置？像这样的东西:

int colours[4][4] = GenerateSomeConfig(); // Gets some combination of colours
int i = GetIndex(colours); // This is the main function I was asking about
int colours2[4][4] = GetConfig(i); // This is the reverse of GetIndex()

assert(CompareGridsEqual(colours, colours2)); // This shouldn't break