生成ai = 1的线性不定方程的所有解的有效算法

Question

我试图为给定的H生成以下方程的所有解.

H = 4时:

1) ALL solutions for x_1 + x_2 + x_3 + x_4 =4
2) ALL solutions for x_1 + x_2 + x_3 = 4
3) ALL solutions for x_1 + x_2 = 4
4) ALL solutions for x_1 =4

对于我的问题,总有4个方程要解决(独立于其他方程).总共有2 ^(H-1)个解决方案.对于前一个,这里是解决方案:

1) 1 1 1 1
2) 1 1 2 and 1 2 1 and 2 1 1
3) 1 3 and 3 1 and 2 2
4) 4

这是一个解决问题的R算法.

library(gtools)
H<-4
solutions<-NULL

for(i in seq(H))
{
    res<-permutations(H-i+1,i,repeats.allowed=T)
    resum<-apply(res,1,sum)
    id<-which(resum==H)

    print(paste("solutions with ",i," variables",sep=""))
    print(res[id,])
}

但是,该算法进行的计算比需要的多.我相信有可能走得更快.由此,我的意思是不生成总和> H的排列

想知道给定H的更好算法吗？

Answer 1

与许多问题一样,当某些术语已知时,解决方案变得更容易找到/研究.

这些问题的解决方案称为整数组合,它们是整数分区的概括(其中顺序无关紧要,即只考虑排列下唯一的答案).

例如,整数分割的4:1 + 1 + 1 + 1,1 + 1 + 2,1 + 3,2 + 2,4,而整数组合物的4:1 + 1 + 1 + 1, 1 + 1 + 2,1 + 2 + 1,2 + 1 + 1,1 + 3,3 + 1,2 + 2,4.

有一些实现很容易获得(参考语言无关的算法如下):

• 由于您在R中工作,因此partitions包可以为您生成分区.您需要找到每个分区的唯一排列以获得合成(请参阅此SO问题).
• 如果你能够使用另一种语言(通过与R接口,或通过预先计算答案),那么Mathematica有一个计算组合的功能:Compositions.
• Sage是免费的(与Mathematica不同),并且还具有生成内置组合的功能:Compositions.值得注意的是,这个是使用生成器实现的,生成器可以更有效地使用内存.
• Python:请参阅此 Stack Overflow问题(生成分区,然后您可以置换).我在这里做了类似的事情(虽然它用于itertools查找排列,然后我需要对唯一排列进行过滤,因此可以通过使用专门用于多集的排列算法来更有效地完成此操作).

为了了解该算法更好(或者自己实现这些功能),你可以看看这个不完整的,但有用的电子书:组合生成由弗兰克·鲁斯基,它展示了如何生成分区不变分期时间(CAT).由于您需要合成,您还可以使用CAT算法生成排列(也在书中)以生成每个整数分区的排列.

Ruskey还解释了如何对它们进行排名和取消,这对于存储/散列结果非常方便.

我相信Knuth的计算机编程艺术第4A卷也很好地介绍了这些内容,如果你碰巧有它的话.

ElKamina建议以递归方式解决它是一个很好的建议,但我不会将这种方法用于大H; 因为R(以及Python)不优化尾调用,所以最终可能会出现堆栈溢出.