Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.0k views
in Technique[技术] by (71.8m points)

algorithm - How to iterate through array combinations with constant sum efficiently?

I have an array and its length is X. Each element of the array has range 1 .. L. I want to iterate efficiently through all array combinations that has sum L.

Correct solutions for: L = 4 and X = 2

1 3
3 1
2 2

Correct solutions for: L = 5 and X = 3

1 1 3
1 3 1
3 1 1
1 2 2
2 1 2
2 2 1

The naive implementation is (no wonder) too slow for my problem (X is up to 8 in my case and L is up to 128).

Could anybody tell me how is this problem called or where to find a fast algorithm for the problem?

Thanks!

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

If I understand correctly, you're given two numbers 1 ≤ XL and you want to generate all sequences of positive integers of length X that sum to L.

(Note: this is similar to the integer partition problem, but not the same, because you consider 1,2,2 to be a different sequence from 2,1,2, whereas in the integer partition problem we ignore the order, so that these are considered to be the same partition.)

The sequences that you are looking for correspond to the combinations of X???1 items out of L???1. For, if we put the numbers 1 to L???1 in order, and pick X???1 of them, then the lengths of intervals between the chosen numbers are positive integers that sum to L.

For example, suppose that L is 16 and X is 5. Then choose 4 numbers from 1 to 15 inclusive:

the four numbers 3, 7, 8, and 14 are chosen from 1 to 15

Add 0 at the beginning and 16 at the end, and the intervals are:

intervals 0–3, 3–7, 7–8, 8–14 and 14–16

and 3 + 4 + 1 + 6 + 2 = 16 as required.

So generate the combinations of X???1 items out of L???1, and for each one, convert it to a partition by finding the intervals. For example, in Python you could write:

from itertools import combinations

def partitions(n, t):
    """
    Generate the sequences of `n` positive integers that sum to `t`.
    """
    assert(1 <= n <= t)
    def intervals(c):
        last = 0
        for i in c:
            yield i - last
            last = i
        yield t - last
    for c in combinations(range(1, t), n - 1):
        yield tuple(intervals(c))

>>> list(partitions(2, 4))
[(1, 3), (2, 2), (3, 1)]
>>> list(partitions(3, 5))
[(1, 1, 3), (1, 2, 2), (1, 3, 1), (2, 1, 2), (2, 2, 1), (3, 1, 1)]

There are (L???1)! / (X???1)!(L???X)! combinations of X???1 items out of L???1, so the runtime of this algorithm (and the size of its output) is exponential in L. However, if you don't count the output, it only needs O(L) space.

With L?=?128 and X?=?8, there are 89,356,415,775 partitions, so it'll take a while to output them all!

(Maybe if you explain why you are computing these partitions, we might be able to suggest some way of meeting your requirements without having to actually produce them all.)


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...