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:
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
Something like this?
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
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
No problem, sometimes I interpret things wrong too while they are typed correctly. 
If I understand it correctly you need something like this?
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
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
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.
As an addition to the given explanations, you may run this edited version :
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
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
Hi DJ.
You can avoid some unnecessary work by rearranging your handler like this:
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.
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!