|
|||||||||
|
|||||||||
| |||||||||
|
|||||||||
|
|||||||||
| |||||||||
|
|
|
| |||||||||
 |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Rate Thread | Display Modes |
Dev Shed Forums Sponsor:
|
|
|
|
#1
August 6th, 2003, 12:33 PM
|
|||
|
|||
|
algorithm help please
I'm trying to figure out a good algorithm to use for a pet application, but I'm having trouble. If anyone can point something out, that'd be great.
What I'm trying to do is this: from a set C = {1, 2, 3, ..., n-1, n}, generate a sequence of d digits = {1, 2, 3, ..., d-1, d}, where the number digits <= n, and where the value of digit x is less than the value of x+1. Thus, the sequence is always increasing. For example, if you have a set C = {1, 2, 3} and need 2 digits, you would generate: 12 13 23 Or with C = {1, 2, 3, 4, 5} and 3 digits: 123 134 234 345 124 135 235 125 145 245 I have studied the pattern extensively using Excel, but cannot come up with a function that takes two arguments and gives me the number of possible permutations. My ultimate goal is to have a mapping function (perhaps a hash) so I can quickly check to see if such and such permutation has been generated. The size of the sets I am dealing with is in the 50-60 range, with 5-7 digits. I have noticed a striking similarity to pascals triangle and the fibonacci series, but all attempts to derive an equation based off of pascals and fibonacii have failed. Can anyone help out here? JasonD
|
|
#2
August 6th, 2003, 02:38 PM
|
||||
|
||||
|
This is just another recursive program. At each point in the program, you have one value that will change, so you have to think, "when all the other values don't change, what range can the current value change to?"
so in your example of a 3 char output with "1,2,3,4,5" as your input: start with 1 next value is 2 (1,2) next value is 3 (1,2,3) since length is used, find all other combinations for 3rd value: (1,2,4) (1,2,5) advance 2nd value to next possible combination, 3 (1,3) next value is 4 (1,3,4) since length is used, find all other combinations for 3rd value: (1,3,5) advance 2nd value to next possible combination, 4 (1,4) next value is 5 (1,4,5) since length is used, find all other combinations for 3rd value: (none) advance 2nd value to next possible combination, 5 (1,5) there is no next value, so exit and advance 1st value (2) advance 2nd value to next possible combination, 3 (2,3) notice a pattern? The logic is the same for each value in your list. Loop through possible combinations, at each change, allow sub values to loop through all their possible combinations. Exit when there are no combinations left.
|
|
#3
August 6th, 2003, 07:14 PM
|
|||
|
|||
|
Right. However, that was not my question. Given an output length and the input set, how can hashing function of sorts be designed?
And without enumerating all possibilities. I realize I said I was trying to generate a sequence... Didn't mean it to come across like that. Thats the easy part. The thing is, the user would be inputting a string that fits the parameters set forth in my earlier post. The program checks to see if that string has been entered, and if not, add it to whatever list or hash or whatever. So the user will start with an empty list to check against, but who knows how many will be entered? 32 million? A linked list would be horrible for searching that. The program is designed to use a possible of 50-60 input characters and 5-8 or so output length. Using Excel, I've calculated the number of permutations to be in the 32 million range. Consider this: if you had a chess board with 64 squares, let each square be one of the input digits. A pawn in the square means it is in the output, nothing in the square means it is not in the output. If you used 6 pawns, how many combinations would there be? Each pawn is identical. Using factorials, 64! / ( 58! * 6! ) = 74 million or so. So how could you efficiently tell if that position (or string) has been entered before?
|
|
#4
August 7th, 2003, 07:34 AM
|
|||
|
|||
|
you can simplify the problem by subtracting the position of each item in the string from the item itself.
so, for example, 1, 2, 3 would be tranlsted to 0, 0, 0 and 2, 4, 8 would be translated to 1, 2, 5... now your input becomes a set of numbers in the following ranges: Code:
first: 0 to n - length of input second: 0 to n - length of input third: 0 to n - length of input you will then be able to quickly resolve a given string to it's position in the n!(n-k)!/k! possibilities for storage by a recursive function call without the need for storing the actual possibilities. i guess that this should suit your purpose, assuming n and k never change etc. these are definitely combinations and not permutations, btw. Last edited by epl : August 7th, 2003 at 10:50 AM.
|
|
#5
August 7th, 2003, 08:55 AM
|
|||
|
|||
|
Thanks for the help. Thats a great idea.
JasonD
|
|
#6
August 7th, 2003, 10:46 AM
|
|||
|
|||
|
i attach calculations in an excel book with the above implemented in vba using a recursive function call.
the code isn't commented but the procedure is effectively this: 1. translate each value onto one of 0, 1, n-k 2. call the first value in the list i0 3. if this is the only value the return it 4. calculate where the index of the first value changes to i0 in the n!(n-k)!/k! space 5. drop the first value, i0, from the array 6. reduce n by 1+i0 and k by 1 7. add the value calculated in 4. to the function recursed for the new values of n and k and the new array, without the first element 8. return the total hopefully this is clear enough with the information in the sheets. ps my combinations function doesn't return 1 for nC0 - it should Last edited by epl : August 7th, 2003 at 11:33 AM.
|
|
#7
August 7th, 2003, 12:35 PM
|
|||
|
|||
|
here's a function which calculates the position directly (without any need to translate indices as above):
Code:
uint getIndex(uint n,uint k,uint[] i)
{if (k==1u) {return i[0];}
else
{uint index=0u;
for (uint a=1u;a<i[0];++a) {index+=c(n-a,k-1);}
for (uint a=k-1u;0u<a;--a) {i[a]-=i[a-1];i[a]-=1;}
i[0]-=1;
for (uint a=0u;1<k;++a)
{n-=i[a]+1u;k-=1u;
for (uint b=1u;b<=i[a+1u];++b)
{index+=c(n-b,k-1u);}
} return index;
}
}
note also that the c(n,k) function should be the standard nCk function as follows: Code:
public static uint c(uint n,uint k)
{if (k==0) {return 1u;}
if (n<k) {return 0u;}
if (n/2u<k) {k=n-k;}
if (k==1u) {return n;}
uint num=1u;uint den=1u;
while (0u<k) {num*=n--;den*=k--;}
return num/den;
}
|
|
#8
August 8th, 2003, 07:32 AM
|
|||
|
|||
|
Here's the same functionality with one less nested loop so it should be significantly faster...
it uses n-1Ck = nCk - n-1Ck-1 to eliminate the need for adding up the nCk's Code:
public static uint getIndex(uint n,uint k,uint[] i)
{if (k==1u) {return i[0];}
else
{for (uint a=k-1u;0u<a;--a) {i[a]-=i[a-1];i[a]-=1;}
i[0]-=1;uint index=c(n,n-k)-c(n-i[0],n-k-i[0]);
for (uint a=0u;1<k;)
{n-=i[a++]+1u;--k;
if (1u==i[a]) {index+=c(n-1,n-k);}
if (1u< i[a]) {index+=c(n,n-k)-c(n-i[a],n-k-i[a]);}
} return index;
}
}
Code:
public static uint c(uint n,uint k)
{if (k==0||k==n) {return 1u;}
if (n<k) {return 0u;}
if (n/2u<k) {k=n-k;}
if (k==1u) {return n;}
uint num=1u;uint den=1u;
while (0u<k) {num*=n--;den*=k--;}
return num/den;
}
Code:
public static uint c2(uint n,uint k)
{if (k==0||k==n) {return 1u;}
if (n<k) {return 0u;}
if (n/2u<k) {k=n-k;}
if (k==1u) {return n;}
uint[] numerator=new uint[k];uint[] denomimator=new uint[k];
for (uint i=0;i<k;++i) {numerator[i]=n-i;denomimator[i]=i+1;}
for (uint i=k;1<i;--i)
{for (uint j=n%i;j<k;j+=i)
{if (0==numerator[j]%i)
{numerator[j]/=i;denomimator[i-1]=1;break;}}
} uint num=1, den=1;
for (uint i=0;i<k;++i) {num*=numerator[i];den*=denomimator[i];}
return num/den;
}
Last edited by epl : August 8th, 2003 at 09:04 AM.
|
|
#9
September 24th, 2004, 11:05 AM
|
|||
|
|||
|
permutation / combination problem VB.NET PLEASE HELP!
I have a similar problem. I have an array that looks somthing like this:
1, a 2, b 3, c 3, 6 4, e 5, f 5, g the first column represents the sequence possibilities of the second column of digits. I need an algorithm that gives me ALL the number/letter variations (combinations) based upon that structure. In the example above we have a total of 4 number/letter combination possibilites: abcef ab6ef abceg ab6eg The digits cannot move out of thier sequences but do to the variations within a sequence position I'm having difficulty coming up with an inclusive script ... I'm sure recursion will be involved. PLEASE HELP!! Thanks ahead of time. The length of this array can be 1 to n and the number of digits that a sequence may have is also 1 to n. thanks again.
|
|
#10
October 1st, 2004, 05:56 AM
|
|||
|
|||
|
Do you want someone to write the procedure for you?
Put something down to start from - something that works for a simple sample case perhaps - it makes it easier to give you something useful. Last edited by epl : October 1st, 2004 at 06:09 AM.
|
|
| Viewing: Dev Shed Forums > Programming Languages - More > Software Design > algorithm help please |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
|
|
 |
|
|
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
Linear Mode
