0

I have a for loop from range 0 to 1000 in which i want get all possible combinations of how the current number can be split up into for example 4 numbers and also use xor on these combinations :

split_up_in = 4
for i in range(0, 1000):
    combinations = getAllCombinationsXORs(i, split_up_in)
    print(combinations)

Update

Example:

i = 6

Split up into 4 numbers (only positive numbers without zero)

1 1 2 2 xor: 0 or 1 1 1 3 xor: 2 and so on filling in all the possibilities to sum up to the number i = 6

The order is not important. 1 1 2 2 is the same as 1 2 1 2

Is there any faster way to do it in python? Maybe an in-built function.

TheDoctor
  • 2,362
  • 4
  • 22
  • 39
  • What do you mean by "spliting numbers"? Does that mean the sum of output will be the original number? – Dabiuteef Nov 19 '17 at 02:51
  • Yes the sum is the original number. I added an example – TheDoctor Nov 19 '17 at 02:56
  • Maybe [this](https://stackoverflow.com/questions/14053885/integer-partition-algorithm-and-recursion) will help. – Dabiuteef Nov 19 '17 at 02:58
  • combination is where the order doesnt matter, and I think you can do it by appending numbers to list and summing it up but Im not sure on how fast it would run. – Abhishta Gatya Nov 19 '17 at 03:07
  • 2
    Possible duplicate of [Integer Partition (algorithm and recursion)](https://stackoverflow.com/questions/14053885/integer-partition-algorithm-and-recursion) – jhpratt Nov 19 '17 at 04:04
  • Some clarifications, please. 1) Can zero be one of the numbers in a partition? 2) Does the order of the numbers in a partition matter (does `1 1 2 2` differ from `1 2 1 2`)? 3) Do you need to find all the partitions for `1` then for `2` then for `3`... or can they be found in a different order? – Rory Daulton Nov 19 '17 at 10:10
  • @jhpratt i wanted to know if there is an efficient way to do this in python. So i don't think my question is a duplicate! – TheDoctor Nov 19 '17 at 14:08
  • @RoryDaulton 1) & 2) i updated my question 3) they can be found in any order – TheDoctor Nov 19 '17 at 14:09
  • If the order does not matter, you should change your example of `1 3 1 1` to `1 1 1 3`. It is usual in cases where order does not matter to show the result in increasing order. My algorithm returns in that order, for example. (I'll show it later if I have time--which will probably not happen.) – Rory Daulton Nov 19 '17 at 18:10

3 Answers3

1

This is not best efficient method since it will take little time , But just an opinion and i suggest try this only when you don't have any other option because it will take time :

import itertools

def all_combination(range_d,split_up_to):
    getAllCombinations={}
    for item in range(0,range_d):
        check=[sub_item for sub_item in range(0,item)]
        for item_1 in itertools.product(check,repeat=split_up_to):
            if sum(item_1)==item:
                if "Number {}".format(item) not in getAllCombinations:
                    getAllCombinations["Number {}".format(item)]=[item_1]
                else:
                    getAllCombinations["Number {}".format(item)].append(item_1)
    return getAllCombinations

print(all_combination(7,4))

output:

{'Number 6': [(0, 0, 1, 5), (0, 0, 2, 4), (0, 0, 3, 3), (0, 0, 4, 2), (0, 0, 5, 1), (0, 1, 0, 5), (0, 1, 1, 4), (0, 1, 2, 3), (0, 1, 3, 2), (0, 1, 4, 1), (0, 1, 5, 0), (0, 2, 0, 4), (0, 2, 1, 3), (0, 2, 2, 2), (0, 2, 3, 1), (0, 2, 4, 0), (0, 3, 0, 3), (0, 3, 1, 2), (0, 3, 2, 1), (0, 3, 3, 0), (0, 4, 0, 2), (0, 4, 1, 1), (0, 4, 2, 0), (0, 5, 0, 1), (0, 5, 1, 0), (1, 0, 0, 5), (1, 0, 1, 4), (1, 0, 2, 3), (1, 0, 3, 2), (1, 0, 4, 1), (1, 0, 5, 0), (1, 1, 0, 4), (1, 1, 1, 3), (1, 1, 2, 2), (1, 1, 3, 1), (1, 1, 4, 0), (1, 2, 0, 3), (1, 2, 1, 2), (1, 2, 2, 1), (1, 2, 3, 0), (1, 3, 0, 2), (1, 3, 1, 1), (1, 3, 2, 0), (1, 4, 0, 1), (1, 4, 1, 0), (1, 5, 0, 0), (2, 0, 0, 4), (2, 0, 1, 3), (2, 0, 2, 2), (2, 0, 3, 1), (2, 0, 4, 0), (2, 1, 0, 3), (2, 1, 1, 2), (2, 1, 2, 1), (2, 1, 3, 0), (2, 2, 0, 2), (2, 2, 1, 1), (2, 2, 2, 0), (2, 3, 0, 1), (2, 3, 1, 0), (2, 4, 0, 0), (3, 0, 0, 3), (3, 0, 1, 2), (3, 0, 2, 1), (3, 0, 3, 0), (3, 1, 0, 2), (3, 1, 1, 1), (3, 1, 2, 0), (3, 2, 0, 1), (3, 2, 1, 0), (3, 3, 0, 0), (4, 0, 0, 2), (4, 0, 1, 1), (4, 0, 2, 0), (4, 1, 0, 1), (4, 1, 1, 0), (4, 2, 0, 0), (5, 0, 0, 1), (5, 0, 1, 0), (5, 1, 0, 0)], 'Number 4': [(0, 0, 1, 3), (0, 0, 2, 2), (0, 0, 3, 1), (0, 1, 0, 3), (0, 1, 1, 2), (0, 1, 2, 1), (0, 1, 3, 0), (0, 2, 0, 2), (0, 2, 1, 1), (0, 2, 2, 0), (0, 3, 0, 1), (0, 3, 1, 0), (1, 0, 0, 3), (1, 0, 1, 2), (1, 0, 2, 1), (1, 0, 3, 0), (1, 1, 0, 2), (1, 1, 1, 1), (1, 1, 2, 0), (1, 2, 0, 1), (1, 2, 1, 0), (1, 3, 0, 0), (2, 0, 0, 2), (2, 0, 1, 1), (2, 0, 2, 0), (2, 1, 0, 1), (2, 1, 1, 0), (2, 2, 0, 0), (3, 0, 0, 1), (3, 0, 1, 0), (3, 1, 0, 0)], 'Number 5': [(0, 0, 1, 4), (0, 0, 2, 3), (0, 0, 3, 2), (0, 0, 4, 1), (0, 1, 0, 4), (0, 1, 1, 3), (0, 1, 2, 2), (0, 1, 3, 1), (0, 1, 4, 0), (0, 2, 0, 3), (0, 2, 1, 2), (0, 2, 2, 1), (0, 2, 3, 0), (0, 3, 0, 2), (0, 3, 1, 1), (0, 3, 2, 0), (0, 4, 0, 1), (0, 4, 1, 0), (1, 0, 0, 4), (1, 0, 1, 3), (1, 0, 2, 2), (1, 0, 3, 1), (1, 0, 4, 0), (1, 1, 0, 3), (1, 1, 1, 2), (1, 1, 2, 1), (1, 1, 3, 0), (1, 2, 0, 2), (1, 2, 1, 1), (1, 2, 2, 0), (1, 3, 0, 1), (1, 3, 1, 0), (1, 4, 0, 0), (2, 0, 0, 3), (2, 0, 1, 2), (2, 0, 2, 1), (2, 0, 3, 0), (2, 1, 0, 2), (2, 1, 1, 1), (2, 1, 2, 0), (2, 2, 0, 1), (2, 2, 1, 0), (2, 3, 0, 0), (3, 0, 0, 2), (3, 0, 1, 1), (3, 0, 2, 0), (3, 1, 0, 1), (3, 1, 1, 0), (3, 2, 0, 0), (4, 0, 0, 1), (4, 0, 1, 0), (4, 1, 0, 0)], 'Number 2': [(0, 0, 1, 1), (0, 1, 0, 1), (0, 1, 1, 0), (1, 0, 0, 1), (1, 0, 1, 0), (1, 1, 0, 0)], 'Number 3': [(0, 0, 1, 2), (0, 0, 2, 1), (0, 1, 0, 2), (0, 1, 1, 1), (0, 1, 2, 0), (0, 2, 0, 1), (0, 2, 1, 0), (1, 0, 0, 2), (1, 0, 1, 1), (1, 0, 2, 0), (1, 1, 0, 1), (1, 1, 1, 0), (1, 2, 0, 0), (2, 0, 0, 1), (2, 0, 1, 0), (2, 1, 0, 0)]}
Aaditya Ura
  • 12,007
  • 7
  • 50
  • 88
0

You have about n^3 partitions of every number into 4 parts, so using 3 nested loops is the best way to divide every number into parts.

Note however, that you can store partitions and reuse then for bigger numbers - but you need a very very lot of space.

MBo
  • 77,366
  • 5
  • 53
  • 86
0

Partitioning a number n into k parts must have a complexity of O(n^(k-1)), since the number of partitions itself is proportional to that. Therefore there is no faster algorithm for this problem.

If you want to print the results from 0 to 1000, then you should store the partitions and reuse them. Note that you only need to store the last k results because the recurrence relation has an order of k.

Dabiuteef
  • 465
  • 4
  • 14