How to partition integer with non-duplicated element sequences ?

[shingerald]

4=1+3
4=1+1+2
4=1+1+1+1
4=2+2

4=2+1+1 is equivalent to 4=1+1+2

It has been taking me for times, but i haven't found a solution..

[Krishnaa]

I don;t get your question.. is it just at algorithm level ?

[ProgramThis]

Basically you want to search for all Combinations (http://en.wikipedia.org/wiki/Mathematical_combination) versus Permutations (http://en.wikipedia.org/wiki/Permutation) right?

if you restrict all lower digits to the left side of the series making up a set then you cannot help but exclude duplicates. What I mean is keep the numbers in order, that way you will not get duplicate combinations.

[TheCPUWizard]

You can also take a recursive approach, just start each recursion at n.

This will efective keep the number in order as ProgramThis suggested.

[shingerald]

Basically you want to search for all Combinations (http://en.wikipedia.org/wiki/Mathematical_combination) versus Permutations (http://en.wikipedia.org/wiki/Permutation) right?

if you restrict all lower digits to the left side of the series making up a set then you cannot help but exclude duplicates. What I mean is keep the numbers in order, that way you will not get duplicate combinations.
i think it is time-consuming to do so, each sequece needs a sorting and then traverse the existed sequences

[shingerald]

You can also take a recursive approach, just start each recursion at n.

This will efective keep the number in order as ProgramThis suggested.
yes, i did it in recursion, but failed to output the right result when n equals to 6, the sequence-2+2+2 lacks...here is my algorithm,

1.from i = 1 to n/2
2.output i + (n-i)
3.if (n-i) have not partitioned, recursively call the procedure with parameter n-i, else return.

[pm_kirkham]

You also should be passing the value you remove to your recursive method, so you don't remove a value greater than it.

so you'd call part(n - t, t) for t up to n-1

part(n,r) => t + part(n-t, t) for min(n,r) >= t >= 1
part(1,_) => 1

start with part(N,N-1) if you don't want the 4 = 4 case.


Specifically, if your first 2 steps are 6 + 2, you have n=4, r=2. If you only passed in n, then you'd get 4=3+1 as the first case, generating 6=2+3+1, so just passing in n and recursing isn't enough to ensure you generate the combinations in order.

[shingerald]

You also should be passing the value you remove to your recursive method, so you don't remove a value greater than it.

so you'd call part(n - t, t) for t up to n-1

part(n,r) => t + part(n-t, t) for min(n,r) >= t >= 1
part(1,_) => 1

start with part(N,N-1) if you don't want the 4 = 4 case.


Specifically, if your first 2 steps are 6 + 2, you have n=4, r=2. If you only passed in n, then you'd get 4=3+1 as the first case, generating 6=2+3+1, so just passing in n and recursing isn't enough to ensure you generate the combinations in order.
i didn't get your idea clearly, what's the usage of parameter "r"?

[pm_kirkham]

You don't want to generate combinations which are out of order, such as 6 = 2+3+1, so you pass the value you removed in the previous stage so you don't attempt to remove a value larger than it in the current stage. That value I called r.