Combinations or Permutations or something else??
-
I have the following string "1100" (or any string of size N with N/2 '1' followed by N/2 '0). I want to make a function that returns all the possible arrangements of "1100" for example: 1100 1010 1001 0110 0101 0011 How would I go about doing this?
I love to program!
-
I have the following string "1100" (or any string of size N with N/2 '1' followed by N/2 '0). I want to make a function that returns all the possible arrangements of "1100" for example: 1100 1010 1001 0110 0101 0011 How would I go about doing this?
I love to program!
Try This: create the following functions: =============================== 1.string arraytoString(int []) This function must combine the array into string. 2.int countOnes(int []) This function must count the number of "ones" present in the array. 3.int [] convertToBinary(int n,int s) This function must convert the integer n to its binary equivaling and split them into an array of size s. Ex: input:8,5 output: {0,1,0,0,0}
4.mainfunction()
{
for(int i=0;i<2N;i++)//N->size
{
int a[]=convertToBinary(i,N);
if(countOnes(a)==N/2)
print arraytoString(a);
}}
Regards, Arun Kumar.A
-
I have the following string "1100" (or any string of size N with N/2 '1' followed by N/2 '0). I want to make a function that returns all the possible arrangements of "1100" for example: 1100 1010 1001 0110 0101 0011 How would I go about doing this?
I love to program!
Hi, there is at least one way to generate the strings you want without trying more combinations and then rejecting the ones that dont fit the constraints. Lets say we want all the strings containing M ones and M zeroes. Assume a recursive method that at each level generates zero to MAX zeroes followed by a single one (hence MAX+1 different strings). If we call this methods M times (concatenating the output of each recursion level), we will get M ones and some number of zeroes. By carefully calculating MAX on each level, we can get exactly M zeroes as well. So initially MAX equals M. If fewer than M recursions have been executed, recurse with MAX reduced by the amount of zeroes already emitted; also after M recursions add the missing zeroes if any. So for M=2 it would generate in order:
001 1 /
01 01 /
01 1 0
1 001 /
1 01 0
1 1 00where the first column holds the output of the first level, the second the output of the second level of recursion, and the third column the added missing zeroes. When the sequence of zeroes in each level is generated from MAX downto zero zeroes, the net result is the numbers appear in numerical order. No trial and error involved ! BTW this is not a C# question at all, it would fit better in math & algos forum ! :) -- modified at 21:57 Wednesday 25th April, 2007
Luc Pattyn [My Articles]
-
Hi, there is at least one way to generate the strings you want without trying more combinations and then rejecting the ones that dont fit the constraints. Lets say we want all the strings containing M ones and M zeroes. Assume a recursive method that at each level generates zero to MAX zeroes followed by a single one (hence MAX+1 different strings). If we call this methods M times (concatenating the output of each recursion level), we will get M ones and some number of zeroes. By carefully calculating MAX on each level, we can get exactly M zeroes as well. So initially MAX equals M. If fewer than M recursions have been executed, recurse with MAX reduced by the amount of zeroes already emitted; also after M recursions add the missing zeroes if any. So for M=2 it would generate in order:
001 1 /
01 01 /
01 1 0
1 001 /
1 01 0
1 1 00where the first column holds the output of the first level, the second the output of the second level of recursion, and the third column the added missing zeroes. When the sequence of zeroes in each level is generated from MAX downto zero zeroes, the net result is the numbers appear in numerical order. No trial and error involved ! BTW this is not a C# question at all, it would fit better in math & algos forum ! :) -- modified at 21:57 Wednesday 25th April, 2007
Luc Pattyn [My Articles]
Thats great.
Regards, Arun Kumar.A