10 Replies Latest reply on Jun 28, 2013 12:41 PM by FileKraft

    Script needed for generating permutations

    dvalley

      I have been racking my brain over this one all day: I need a recursive script to generate a record for each of the non-repeating permutations for a series of five fields utilizing a total of n numbers (say, up to 35). I know that the total number of records genrated will be 38,955,840, but it is the structure of the script that is of interest. I have seen custom functions that come close, but with the recursion limit, they are of no use to me.

        • 1. Re: Script needed for generating permutations
          ch0c0halic

          dvalley,

           

          First a custom function cannot create a record. You'd have to use a script in any case.

           

          Is this the correct definition of what you want to do?

          5 fields with up to 35 different values in each field?

           

          35 X 35 X 35 X 35 X 35 = 52,521,875 unique records.

           

          How are you getting these initial values? Are you defining a start and stop number or value for each of the 5 fields? Is it always numbers or will there also be letters. Are these values sequential or random?

           

          It is a very different approach using numbers starting at 1 and ending at 35 for each of the five fields verses some of them being letters of the alphabet.

           

          If you are not intimately familiar with FMP scripting and looping constructs this may not make enough sense to you. Please ask if i've been too cryptic.

           

           

          Alternative 1:

          If they are each a sequential number series starting at 1 and ending at 35 then create 35 blank records and assign the first value of 1, 1, 1, 1, 1 to the first record and do a replace with serial number on the first value, starting at 1, with incrementing the value by 1. This gives you the first series of 35 records.

           

          Create 35 more records. Do the same as for first series but use 2 for the second fields value.

           

          Repeat for 3 - 35 in field 2.

           

          By using a loop inside a loop structure and keeping track of the field you are modifying you can do this for each field and create as many records as you want.

           

          However, this is not a fast process and isn't appropriate for an alpha character based process.

           

           

          Alternative 2:

           

          Create five separate sub-scripts to loop through and set a variable with values you need. For example set $var1 to "1". With each iteration you increment the value of $var1, where it can be any value of text or numbers.

           

          Set script one to call script two and script two to call script 3 and script 3 to call script 4 and script 4 to call script 5  and have script 5 create a new record and set fields 1-5 with $var1 - 5 respectively for each of its iterations.

           

          Set exit condition at end of loop of script 1 so it stops when the highest expected value is reached in each of the variables.

          • 2. Re: Script needed for generating permutations
            sporobolus

            on 2013-06-26 14:35 dvalley wrote

            I need a recursive script to generate a record for each of  the non-repeating permutations for a series of five fields utilizing a total of n numbers (say, up to 35).  I know that the total number of records genrated will be 38,955,840, but it is the structure of the script that is of interest.  I have seen custom functions that come close, but with the recursion limit, they are of no use to me.

             

            there are so many tools already equipped for this that i would consider

            creating permutations with another tool, output to a file, then import the

            file; for example this python script:

             

            #!/bin/python
            import itertools, sys
            print sys.argv[1]
            for values in itertools.permutations(sys.argv[1:], 5):
               print "%s\t%s\t%s\t%s\t%s" % values
            

             

            saved as file "perms_k5.py" and run like this:

             

            python perms_k5.py 1 2 3 4 5 46 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 
            24 25 26 27 28 29 30 31 32 33 34 35 >foo.dat
            

             

            took about 80 seconds to run on my midrange OS X system, creating a 510 MB file

            with 38955841 lines (one line is blank, ch0c0halic's calculation includes

            repeats) containing the non-repeating permutations … importing into FileMaker

            will take a bit longer

            • 3. Re: Script needed for generating permutations
              ftn

              on 2013-06-26 16:30 i wrote

                 print sys.argv[1]
              

               

              sorry, the above line was left in from testing; remove it and the output line

              count makes perfect sense

              • 4. Re: Script needed for generating permutations
                dvalley

                Thank you for the response ch0c0halic.  Perhaps, I did not explain the problem adequately.  Allow me to rephrase:  I have a deck of cards with a total of 35 cards.  I lay out a hand of five cards.  Each card is unique.  I need a script to create new hands ultimately containing every permutataion of five card hand possible.

                • 5. Re: Script needed for generating permutations
                  ch0c0halic

                  dvalley,

                   

                  So for your purposes 12345 and 54321 and 51423 are all the same hand as the combination of cards is the same even though the order is different. That does make it more difficult.

                   

                  Create a new field using a calculation that concatenates the 5 card fields but in ascending order (maybe using a custom function). Set it to always be unique. This may have to be an Auto-Enter-Calculation (AEC) so make sure it doesn't fire till all 5 fields are filled in.

                   

                  Now set up the looping scripts I suggested and if the new record commit fails then increment the last field, or if its at max then increment the previous field and reset the last field just like the loop would do, etc. till one is not at max and the commit works.

                   

                   

                  Variables Alternative to using fields.

                  FMP will need a lot of memory so be sure to up the cage to 256MB or even 512MB.

                   

                  If the 'cards' are a numeric sequence it's possible you could set up the looping scripts using a results variable, instead of 5 fields, with the 'hand' as the pointer into the variable. If the pointer already exists then do nothing, if it doesn't then use it to set the value to 1. To create the records just run through all the potential variable values in the pointer and if "1" then create the record with the pointer value.

                   

                  For example:

                  sequence_hand ( $var1 ; $var2 ; $var3 ; $var4 ; $var5 )

                  //Custom Function to order values in ascending order.

                   

                  $results[sequence_hand]

                  //will point to a specific instance of $results.

                   

                  If [ IsEmpty ( $results[$var1 & $var2 & $var3 & $var4 & $var5] )

                  //tells you if the 'hand' exists'

                   

                  Set Variable $results[$var1 & $var2 & $var3 & $var4 & $var5] to 1

                  //tells us the variable has already been set so the current sequence it a duplicate

                   

                  Once this has completed then

                  $results[12345] = 1

                  tells us this 'pointer' is a valid hand. Running through all the pointers from

                  $results[11111]

                  to

                  $results[55555]

                   

                  and creating a new record if the value is 1 will produce only unique records.

                   

                  This process is identical to the first except it uses variable and so it may be faster in the creation of unique values.

                   

                  PS. I did this off the top of my head so I may not have given all the steps needed to make this work. Hopefully you've got the idea and can run with it.

                  • 6. Re: Script needed for generating permutations
                    sporobolus

                    on 2013-06-27 6:01 dvalley wrote

                    Thank you for the response ch0c0halic.  Perhaps, I did not explain the problem adequately.  Allow me to rephrase:  I have a deck of cards with a total of 35 cards.  I lay out a hand of five cards.  Each card is unique.  I need a script to create new hands ultimately containing every permutataion of five card hand possible.

                     

                    that's how i took it and based on the fact i got the number of rows you

                    expected, my method seems to give the correct result; you mentioned

                    non-repeating in the first statement, and i took you to mean that the

                    conventional way — these two are not the same:

                     

                    1, 2, 3, 4, 5

                    5, 4, 3, 2, 1

                     

                    however, as ch0c0halic has guessed, you may want a constraint on the

                    permutations that only one possible combination of a given set of 5 cards

                    should appear (so only one of the above two rows would be produced); if that's

                    the case here is a Python/shell solution:

                     

                    #!/bin/python
                    import itertools, sys
                    for values in itertools.permutations(sys.argv[1:], 5):
                       print "%s\t%s\t%s\t%s\t%s" % tuple(sorted([i for i in values]))
                    

                     

                    saved again as file "perms_k5.py" and run like this:

                     

                    python perms_k5.py 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 
                    24 25 26 27 28 29 30 31 32 33 34 35 | sort -u > foo2.dat
                    

                     

                    took about 20 minutes and produced 324632 rows; the python portion was only

                    around 4.5 minutes, but sort really slowed it down; still, not bad for a quick

                    & dirty solution and probably much faster than native FileMaker; not to mention

                    the time you'll spend coding

                    • 7. Re: Script needed for generating permutations
                      DavidJondreau

                      Let's not get ahead of ourselves... What are you really trying to do here? In other words, what experience do you want the users to have?

                       

                       

                      For example, If what you want is for users to see 5 random cards from a deck of 35, you don't need 40 Million records. You need a couple lines of code.

                      • 8. Re: Script needed for generating permutations
                        sporobolus

                        here's a pure Python solution replacing my last suggestion; it is much faster

                        and can produce "hands" of any length:

                         

                        #!/bin/python
                        # non-repeating permutations of k items from the argument set of items,
                        # constrained to produce only one combination of each set of k items
                        # args: k item1 item2 ... itemk [itemk+1 ...]
                        
                        import itertools, sys
                        
                        def unique(iterable):
                           seen = set()
                           for x in iterable:
                             xs = frozenset(x)
                             if xs in seen:
                               continue
                             seen.add(xs)
                             yield xs
                        
                        k = int(sys.argv[1])
                        s = sys.argv[2:]
                        
                        if len(s) < k:
                            print "args: k item1 item2 ... itemk [itemk+1 ...]"
                        for a in unique(itertools.permutations(s, k)):
                            print "\t".join(a)
                        

                         

                        saved as partial_perms_constrained.py and run via:

                         

                        python partial_perms_constrained.py 5 a b c d e f g h i j k l m n o p q r s t u 
                        v w x y z 1 2 3 4 5 6 7 8 9 > foo3.dat
                        

                         

                        took 28 seconds to produce the 324632 rows

                        • 9. Re: Script needed for generating permutations
                          dvalley

                          Thank you all for your help.  I have come to the conclusion that while FileMaker could perform this task, it is probably not the best choice to do so.  I believe the Python, C or PHP route is the more prudent to take.  To answer some final questions, the purpose of this "exercise" was to aid in game development, in particular, an outoplay environment where such permutations are necessary.  The game was not created in Filemaker, but as I am more familiar with it than other 'languages', I was hoping to develop code that could be adapted.  I was wrong.  Sorry to have put you through such bother, but thank you all the same.

                           

                          D Valley

                          • 10. Re: Script needed for generating permutations
                            FileKraft

                            the amount of permutations of a hand is:

                             

                            Combination ( 35 ; 5 ) = 324,632  *a fm number function

                             

                            filemaker might handle this well - depending on how you approach it and what you really want to do.

                            also a lot of combinatoric structures are static - that means if you know the pattern you can just create all permutations on compile time (when you write the code)  and substitute on run-time with what you want ..

                             

                            good luck.