Some random coding here
Integer partition:
void gen(int lead,int postfix,int number,int *arr,int index,int originalNumber){
if(postfix<1)
return;
do{
int i=index;
arr[i++] = number - postfix;
arr[i] = postfix;
int j = 0;
int sum =0;
for(j=0;j<=index+1;j++){
cout << arr[j] << " ";
sum += arr[j];
}
cout << endl;
counter++;
gen(lead,postfix-1,postfix,arr,index+1,originalNumber-1);
lead++;
postfix = originalNumber - lead;
}while(lead < originalNumber);
}
which I thought is an awful implementation so I stole a python implementation as below
## {{{ http://code.activestate.com/recipes/218332/ (r1)
import sys
def partitions(n):
# base case of recursion: zero is the sum of the empty list
if n == 0:
yield []
return
# modify partitions of n-1 to form partitions of n
for p in partitions(n-1):
yield [1] + p
if p and (len(p) < 2 or p[1] > p[0]):
## print ["DEBUG: "] + p
yield [p[0] + 1] + p[1:]
## end of http://code.activestate.com/recipes/218332/ }}}
print "Enter a number (0 to quit): "
n = int(sys.stdin.readline())
while n>0:
counter = 0
for p in partitions(n):
print p
counter = counter + 1
print "There were " + str(counter) + " unqiue partitions"
print "Enter a number (0 to quit): "
n = int(sys.stdin.readline())
the equivalent C# implementation is
public static IEnumerable<List<int>> intpart(int n)
{
if (n < 0)
yield return null;
if (n == 0)
yield return new List<int>();
foreach (List<int> list in intpart(n - 1))
{
if (list == null) break;
var temp = new List<int>();
temp.Add(1);
temp.AddRange(list);
yield return temp;
if (list.Count > 0 && (list.Count < 2 || list[1] > list[0]))
{
var newList = new List<int>();
newList.Add(list[0] + 1);
newList.AddRange(list.GetRange(1, list.Count - 1));
yield return newList;
}
}
}
and playing with python and generating permutations
def ListPermutations(prefix,original):
if original == "":
print prefix
else:
index = 0
length = len(original)
while index < length:
if index < length-1 and original[index]==original[index+1]:
index = index + 1
continue
newprefix = prefix + original[index]
neworiginal = original[0:index]+original[index+1:]
index = index + 1
ListPermutations(newprefix,neworiginal)
##
and now java
public static void generate(int []array){
while(array[0]
{
int sum = 0;
int n = array.length;
int stopIndex = -1;
for(int i:array){
sum+= i;
stopIndex++;
if(sum>=n){
System.out.print( ((sum-n)>0?(sum-n):i) );
break;
}
System.out.print(i + " ");
}
sum = 0;
counter++;
System.out.println();
int startIndex = 1;
for(int i=stopIndex-1;i>=startIndex;i--)
{
if(array[i]
{
array[i]++;
for(int j=i+1;j
array[j]=1;
generate(array);
}
}
array[0]++;
for(int i=1;i
{
array[i]=1;
}
}
}
as for the additional non-sense, seize your moment for you may not get a second chance and enjoy http://www.youtube.com/watch?v=g9hMLnmeNm4 awfully nice sound and words
