Saturday, December 3, 2022

#1 2014-09-26 12:09:49 am

blend3
Member
From:: UK
Registered: 2006-03-28
Posts: 471

calculate every permutation of multiple lists

Hi all,

I would like to be able to work out every permutation of multiple lists. The problem I have is that each list could be a different length and the amount of lists could vary! for example:

Applescript:

set list1 to {"black", "dark brown", "beige", "blue", "yellow"}
set list2 to {"orange", "green"}
set list3 to {"pink", "lavendar", "red"}

can anyone give me any pointers on how to achieve this?

Many Thanks,
Nik


I can resist everything in life except temptation.
(Oscar Wilde)

Offline

 

#2 2014-09-26 04:47:49 am

DJ Bazzie Wazzie
Member
From:: the Netherlands
Registered: 2004-10-20
Posts: 2809
Website

Re: calculate every permutation of multiple lists

Something like this?

Applescript:

set list1 to {"black", "dark brown", "beige", "blue", "yellow"}
set list2 to {"orange", "green"}
set list3 to {"pink", "lavendar", "red"}

set permutations to {}
permute(list1, 1, 5, a reference to permutations)
return permutations

on permute(theList, theStart, theEnd, allItems)
   if theStart = theEnd then
       set end of allItems to theList
   else
       repeat with x from theStart to theEnd
           --swap
           tell theList to set {item theStart, item x} to {item x, item theStart}
           copy theList to theList --remove references
           permute(theList, theStart + 1, theEnd, allItems)
           --set back
           tell theList to set {item theStart, item x} to {item x, item theStart}
       end repeat
   end if
end permute

Offline

 

#3 2014-09-26 05:08:04 am

blend3
Member
From:: UK
Registered: 2006-03-28
Posts: 471

Re: calculate every permutation of multiple lists

Many Thanks DJ and I am amazed but the results (Wizard you are). It's not quite the result I was after. I will try to explain a little better, If I have 3 lists then the result should contain 3 colours, 1 colour from each of the lists. If 4 lists then the result should contain 4 colours, 1 colour from each of the lists on so on…

so for example:

{"black","orange","pink"}
{"black","orange","lavender"}
{"black","orange","red"}
{"black","green","pink"}
{"black","green","lavender"}
{"black","orange","red"}

so the above is the maximum combinations that can be achieved using "black" from list 1 and all other colour combinations from the other 2 lists (I think).

Please forgive me if I have mislead you but it's difficult for me to explain.

Thanks again,
Nik


I can resist everything in life except temptation.
(Oscar Wilde)

Offline

 

#4 2014-09-26 06:02:21 am

DJ Bazzie Wazzie
Member
From:: the Netherlands
Registered: 2004-10-20
Posts: 2809
Website

Re: calculate every permutation of multiple lists

blend3 wrote:

Please forgive me if I have mislead you but it's difficult for me to explain.


No problem, sometimes I interpret things wrong too while they are typed correctly. smile

If I understand it correctly you need something like this?

Applescript:

set list1 to {"black", "dark brown", "beige", "blue", "yellow"}
set list2 to {"orange", "green"}
set list3 to {"pink", "lavendar", "red"}

set listofLists to {list1, list2, list3}
set permutations to {}
permutateOverLists(listofLists, {}, a reference to permutations)
return permutations

on permutateOverLists(ll, thePath, allItems)
   set level to (count thePath)
   if level = (count ll) then
       set entry to {}
       repeat with x from 1 to count thePath
           set end of entry to item (item x of thePath) of item x of ll
       end repeat
       set end of allItems to entry
   else
       repeat with x from 1 to count (item (level + 1) of ll)
           permutateOverLists(ll, thePath & x, allItems)
       end repeat
   end if
end permutateOverLists

Last edited by DJ Bazzie Wazzie (2014-09-26 06:02:44 am)

Offline

 

#5 2014-09-26 06:25:18 am

blend3
Member
From:: UK
Registered: 2006-03-28
Posts: 471

Re: calculate every permutation of multiple lists

I think that's it. You're nothing short of genius.

If it's not too much trouble could I ask you to explain how this works.

Many, Many Thanks,
Nik


I can resist everything in life except temptation.
(Oscar Wilde)

Offline

 

#6 2014-09-26 07:11:42 am

DJ Bazzie Wazzie
Member
From:: the Netherlands
Registered: 2004-10-20
Posts: 2809
Website

Re: calculate every permutation of multiple lists

blend3 wrote:

If it's not too much trouble could I ask you to explain how this works.


Of course, I'll do my best.

In simple words when you put the arrays on top of each other you have to look at the data as layers with holes in it. The result you want is that you want every possible path from the top to the bottom through every layer. The only rule is that by every step you can go only one level deeper (not up). Looking at the data structure this way makes it all better understandable instead of looking at it as an listed list (at least for me).

Because we don't know the number of layers it's best to recursively  (a handler calling itself) through the layers to the bottom and pass the data structure, the result set and the current path we've already followed. If the number of lists were known (static) it could be implemented with just a nested loop.

The path is the most important variable we need to pass to each recursion. The handler therefore knows exactly were it is. When the length of the path is not equal to the number of layers, we now we're still not at the bottom. If we're not at the bottom we have to call the same handler again for each hole in the current layer making each recursive process for each whole only one layer below and repeat the whole process.

If we reached the bottom, the number of layers equals to length of the path, we need to look at our path and use our path to resolve the items. The index of items in the path represents the layer, so the first item refers to the first layer. The value of the item in the path refers to the hole in the the layer. That explains the "weird" creation of entry.

Last edited by DJ Bazzie Wazzie (2014-09-26 09:31:22 am)

Offline

 

#7 2014-09-26 07:42:21 am

Yvan Koenig
Member
Registered: 2006-09-14
Posts: 4622

Re: calculate every permutation of multiple lists

As an addition to the given explanations, you may run this edited version :

Applescript:

set list1 to {"black", "dark brown", "beige", "blue", "yellow"}
set list2 to {"orange", "green"}
set list3 to {"pink", "lavendar", "red"}

set listofLists to {list1, list2, list3}
set permutations to {}
permutateOverLists(listofLists, {}, a reference to permutations)
return permutations

on permutateOverLists(ll, thePath, allItems)
   set level to (count thePath)
   log "thePath is : " & thePath
   
   if level = (count ll) then
       set entry to {}
       repeat with x from 1 to count thePath
           set end of entry to item (item x of thePath) of item x of ll
           log "entry is : " & entry
       end repeat
       set end of allItems to entry
   else
       repeat with x from 1 to count (item (level + 1) of ll)
           permutateOverLists(ll, thePath & x, allItems)
       end repeat
   end if
end permutateOverLists

The Events report will show you what the handler does.

Yvan KOENIG (VALLAURIS, France) vendredi 26 septembre 2014 15:41:45

Offline

 

#8 2014-09-26 08:29:03 am

blend3
Member
From:: UK
Registered: 2006-03-28
Posts: 471

Re: calculate every permutation of multiple lists

DJ/Yvan,

thank you both for your invaluable info.

No matter how hard I thought about this it was the amount of unknown list that was causing me the problem.

I won't pretend to understand all of this but hopefully when I integrate this routine with the rest of my script it will become a little clearer.

Many Thanks again guys,
Nik


I can resist everything in life except temptation.
(Oscar Wilde)

Offline

 

#9 2014-10-06 02:26:39 pm

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 5588

Re: calculate every permutation of multiple lists

DJ Bazzie Wazzie wrote:

Applescript:

set list1 to {"black", "dark brown", "beige", "blue", "yellow"}
set list2 to {"orange", "green"}
set list3 to {"pink", "lavendar", "red"}

set permutations to {}
permute(list1, 1, 5, a reference to permutations)
return permutations

on permute(theList, theStart, theEnd, allItems)
   if theStart = theEnd then
       set end of allItems to theList
   else
       repeat with x from theStart to theEnd
           --swap
           tell theList to set {item theStart, item x} to {item x, item theStart}
           copy theList to theList --remove references
           permute(theList, theStart + 1, theEnd, allItems)
           --set back
           tell theList to set {item theStart, item x} to {item x, item theStart}
       end repeat
   end if
end permute


Hi DJ.

You can avoid some unnecessary work by rearranging your handler like this:

Applescript:

on permute(theList, theStart, theEnd, allItems)
   if theStart = theEnd then
       set end of allItems to theList
   else
       repeat with x from theStart to theEnd
           copy theList to theCopy
           --swap
           if (x > theStart) then tell theCopy to set {item theStart, item x} to {item x, item theStart}
           permute(theCopy, theStart + 1, theEnd, allItems)
       end repeat
   end if
end permute

It also has the side-effect of placing the original order first into the permutations list.

Last edited by Nigel Garvey (2014-10-06 02:30:27 pm)


NG

Offline

 

#10 2014-10-06 05:56:40 pm

DJ Bazzie Wazzie
Member
From:: the Netherlands
Registered: 2004-10-20
Posts: 2809
Website

Re: calculate every permutation of multiple lists

Nigel Garvey wrote:

Hi DJ.

You can avoid some unnecessary work by rearranging your handler like this:

It also has the side-effect of placing the original order first into the permutations list.


Thank you again Nigel, Swapping the first item with the first item is indeed some flawless code. It was a direct translation from my own C implementation but this indeed much better. Thank you!

Offline

 

Board footer

Powered by FluxBB

RSS (new topics) RSS (active topics)