Combination of list of word

[AlessioForconi]

Hi to all,

I have a list of words:

mario
andrea
gianni
watermelon
apple
pear
...
...

what I would like is to find every possible sorting combination:

andrea
mario
watermelon
pear
apple
gianni
...
...

mario
gianni
pear
andrea
watermelon
apple
...
...

can anyone give me an idea?

thanks

[rkriesel]

Hi, Alessio.

See "https://en.wikipedia.org/wiki/Permutation" section "k-permutations of n"

Since the formula for the number of k-permutations is n factorial, generating the sequences can be very time-consuming. Here's a summary from my code, which follows.

Code: Select all

name count,sequence count,milliseconds
2,2,0
3,6,0
4,24,2
5,120,10
6,720,58
7,5040,434
8,40320,3498
9,362880,36320
10,3628800,341917

For six names, that's 58 milliseconds. For ten names, that's over six minutes.

Code: Select all

command test_kPermutations
   local tNames = "bob,carol,ted,alice,harry,sally,george,gracie,xavier,zelda"
   local tMilliseconds
   local tReport = "name count,sequence count,milliseconds"
   set cursor to busy
   put cr after tReport
   
   repeat with i = 2 to number of items in tNames
      put - the long milliseconds into tMilliseconds
      get kPermutations( item 1 to i of tNames )
      add the long milliseconds to tMilliseconds
      
      put i, number of lines in it, round( tMilliseconds ) & cr after tReport
      put tReport
      wait 10 milliseconds with messages
   end repeat
   put cr after tReport
   
   breakpoint
end test_kPermutations

function kPermutations pItems
   local tSequences, tSequence, tNewSequence
   put pItems into tSequences
   split tSequences by comma as set
   
   repeat for each item tItem in pItems
      repeat for each key tSequence in tSequences
         if tItem is not among the items of tSequence then
            repeat with i = 0 to number of items in tSequence
               get item 1 to i of tSequence
               if it is empty then
                  put tItem into tNewSequence
               else
                  put it, tItem into tNewSequence
               end if
               get item i + 1 to -1 of tSequence
               if it is not empty then
                  put comma & it after tNewSequence
               end if
               put "true" into tSequences[ tNewSequence ]
            end repeat
         end if
      end repeat
   end repeat
   
   filter the keys of tSequences where number of items in each is number of items in pItems
   get the keys of tSequences
   sort it
   return it
end kPermutations

The code works, but maybe someone else can provide faster and/or simpler code.

Why do you want to do this?
-- Dick

[AlessioForconi]

It is enough for me to insert it in a text file, but there are eighteen words and I believe that the number of combinations will be quite high, I don't know if there will be problems to do it.

[rkriesel]

18 words per sequence
18! sequences
5 bits per word (minimum to distinguish 18 individuals)
a billion bytes per gigabyte
~= 70 million gigabytes in your one file

You can be very sure, as you say, "there will be problems to do it."
-- Dick