CODEWITHSUNDEEP
algorithmpermutation
hamman
hamman

Reputation: 33

permutations without repetition

I would like to know, what is the best approach to solve this problem:

Given x, y and y integers: a1, a2, a3 .. ay find all combinations of a1 ± a2 ± ... ± ay = x, y < 20.

My recent approach is to find all permutations of 1 and 0 stored in table T and then, depending on whether number T[i] is 1 and 0, add or subtract ai from sum. The problem is that there are n! permutations of n-element array. Hence, for 20-element array, I have to check 20! possibilities where most of them are repeated. Could you please suggest me any potential approach to solving my problem?

Upvotes: 3

Views: 449

Answers (2)

John Coleman
John Coleman

Reputation: 51998

There are only 2^20 (just over a million) binary vectors of length 20 rather than the infeasible 20!. Use should be able to brute-force that few in less than a second, especially if you use a Gray Code which would allow you to pass from one candidate sum to another in a single step (e.g. to go from a + b - c -d to a + b - c + d just add 2*d.

The excellent branch and bound idea of @MikeWise would be good if y gets much larger. Generate a tree starting with a root node of 0. Give it children of -a1 and +a1. Then 4 grand children by adding and subtracting a2, etc. If you ever get farther than the sum of the remaining ai from the target x -- you can prune that branch. In the worst case, this might be slightly worse than the Gray-code based brute force (because you need to do so much more processing at each node), but in the best case you might be able to prune away most possibilities.

On Edit: Here is some Python code. First I define a generator which, given an integer n, successively returns which bit position needs to flip to step through a Gray code:

def grayBit(n):
    code = [0]*n
    odd = True
    done = False
    while not done:
        if odd:
            code[0] = 1 - code[0] #flip bit
            odd = False
            yield 0
        else:
            i = code.index(1)
            if i == n-1:
                done = True
            else:
                code[i+1] = 1 - code[i+1]
                odd = True
                yield i+1

(This uses an algorithm which I learned years ago in the excellent book "Constructive Combinatorics" by Stanton and White).

Then -- I use this to return all solutions (as lists consisting of the input list of numbers with negative signs inserted as needed). The key point is that I can take the current bit-to-flip and either add or subtract twice the corresponding number:

def signedSums(nums, target):
    n = len(nums)
    patterns = []
    total = sum(nums)
    pattern = [1]*n
    if target == total: patterns.append([x*y for x,y in zip(nums,pattern)])
    deltas = [2*i for i in nums]
    for i in grayBit(n):
        if pattern[i] == 1:
            total -= deltas[i]
        else:
            total += deltas[i]
        pattern[i] = -1 * pattern[i]
        if target == total: patterns.append([x*y for x,y in zip(nums,pattern)])
    return patterns

Typical output:

>>> signedSums([1,2,3,4,5,9],6)
[[1, -2, -3, -4, 5, 9], [1, 2, 3, -4, -5, 9], [-1, 2, -3, 4, -5, 9], [1, 2, 3, 4, 5, -9]]

It only takes about a second to evaluate:

>>> len(signedSums([i for i in range(1,21)],100))
2865

Hence there are 2865 ways to add or subtract the integers in the range 1,2,..,20 to get a net sum of 100.

I assumed that a1 can be either added or subtracted (instead of just added, which is what your question implies if taken literally). Note that if you really want to insist that a1 occurs positively, then you could just subtract it from x and apply the above algorithm to the rest of the list and the adjusted target.

Finally, it is not too hard to see that if you solve the subset sub problem with the set of weights {2*a1, 2*a2, 2*a3, .... 2*ay} and with a target sum of x + a1 + a2 + ... + ay then the subsets selected will correspond exactly to the subsets where the positive signs occur in the solution to the original problem. Thus your problem is easily reducible to the subset-sum problem and it is thus NP-complete to determine if it has any solutions (and NP-hard to list them all).

Upvotes: 2

Nyavro
Nyavro

Reputation: 8866

We have conditions:

a1 ± a2 ± ... ± ay = x, y<20   [1]

First of all, I would generalize the condition [1], allowing all 'a' including 'a1' to be ±:

±a1 ± a2 ± ... ± ay = x   [2]

If we have solution for [2], we can easily get solution for [1]

To solve [2] we can use the following approach:

combinations list x 
    | x == 0 && null list = [[]]
    | null list = []
    | otherwise = plusCombinations ++ minusCombinations where
    a = head list
    rest = tail list
    plusCombinations = map (\c -> a:c) $ combinations rest (x-a)
    minusCombinations = map (\c -> -a:c) $ combinations rest (x+a)

Explanation:

  1. First condition checks if x reached zero and used all numbers from list. This means that solution found and we return single solution: [[]]

  2. Second condition checks that list is empty and as far as x is not 0 this means that no solution can be found, returning empty solution: []

  3. Third branch means that we can two alternatives: to use ai with '+' or with '-' so we concatenate plus and minus combinations

Example output:

*Main> combinations [1,2,3,4] 2
[[1,2,3,-4],[-1,2,-3,4]]
*Main> combinations [1,2,3,4] 3
[]
*Main> combinations [1,2,3,4] 4
[[1,2,-3,4],[-1,-2,3,4]]

Upvotes: 1

Related Questions