#1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Posts
    3
    Rep Power
    0

    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. #2
  3. Doggie
    Devshed Novice (500 - 999 posts)

    Join Date
    Jul 2003
    Location
    Seattle, WA
    Posts
    751
    Rep Power
    13
    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.
  4. #3
  5. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Posts
    3
    Rep Power
    0
    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?
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2001
    Location
    Dublin
    Posts
    413
    Rep Power
    14
    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
    with this list restricted such that each item is greater than or equal to it's predecessor.

    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.
  8. #5
  9. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Posts
    3
    Rep Power
    0
    Thanks for the help. Thats a great idea.

    JasonD
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2001
    Location
    Dublin
    Posts
    413
    Rep Power
    14
    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
    Attached Files
    Last edited by epl; August 7th, 2003 at 11:33 AM.
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2001
    Location
    Dublin
    Posts
    413
    Rep Power
    14
    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 that the array i[] must have k elements
    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;
       }
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2001
    Location
    Dublin
    Posts
    413
    Rep Power
    14
    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;
           } 
         }
    I've also added the (k==0||k==n) to the c function as it was returning 0, not 1 for nCn:
    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;
         }
    as i look at it, a final idea would also be to do the write the c function as follows - to (aim to) minimise avoidable overflows
    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.
  16. #9
  17. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2004
    Posts
    1
    Rep Power
    0

    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.
  18. #10
  19. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2001
    Location
    Dublin
    Posts
    413
    Rep Power
    14
    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.

IMN logo majestic logo threadwatch logo seochat tools logo