List Permutations

Date:    Thu, 15 Feb 1996 15:55:37 -0500
From:    Dave Yang <qwi@ASTRAL.MAGIC.CA>
Subject: Re: How to recombine strings...? (LONG)

>It returns exactly the same list as the first handler. It does it
>way more slowly, mostly because of the extra list overhead.
>It *could* be coded to run faster. It's "appropriate" recursion
>because ...

This is a simpler solution and is almost 10 times faster (see benchmark below):

on doFastPerm
  global theResult

  set theResult = []
  set theList = ["1","2","3","4"]
  startTimer
  permlist(theList, count(theList))
  put "Time:" && the timer
  put count(theResult)
  put theResult
end doFastPerm


on permList theList, n
  set c = 1
  if n > 2 then
    permList(theList, n-1)
  else
    processList(theList)
  end if
  repeat while c < n
    set t = getAt(theList,n)
    if n mod 2 = 1 then -- odd number
      setAt(theList,n,getAt(theList,1))
      setAt(theList,1,t)
    else
      setAt(theList,n,getAt(theList,c))
      setAt(theList,c,t)
    end if
    set c = c + 1
    if n > 2 then
      permList(theList, n-1)
    else
      processList(theList)
    end if
  end repeat
end permList



on processList theList
  global theResult

  add theResult, makeCopy(theList) -- must make a copy, why?
end processList


on makeCopy srcList
  set tmpList = []
  repeat with i in srcList
    add tmpList, i
  end repeat
  return tmpList
end makeCopy

doFastPerm
-- "Time: 9"
-- 24
-- [["1", "2", "3", "4"], ["2", "1", "3", "4"], ["3", "1", "2", "4"], ["1",
"3", "2", "4"], ["2", "3", "1", "4"], ["3", "2", "1", "4"], ["4", "2", "1",
"3"], ["2", "4", "1", "3"], ["1", "4", "2", "3"], ["4", "1", "2", "3"],
["2", "1", "4", "3"], ["1", "2", "4", "3"], ["1", "3", "4", "2"], ["3",
"1", "4", "2"], ["4", "1", "3", "2"], ["1", "4", "3", "2"], ["3", "4", "1",
"2"], ["4", "3", "1", "2"], ["4", "3", "2", "1"], ["3", "4", "2", "1"],
["2", "4", "3", "1"], ["4", "2", "3", "1"], ["3", "2", "4", "1"], ["2",
"3", "4", "1"]]


on doGlenn
  startTimer
  set theNewList = recurseUniqueOrders(["1","2","3","4"])
  put "Time:" && the timer
  put count(theNewList)
  put theNewList
end doGlenn

doGlenn
-- "Time: 88"
-- 24
-- [["1", "2", "3", "4"], ["1", "2", "4", "3"], ["1", "3", "2", "4"], ["1",
"3", "4", "2"], ["1", "4", "2", "3"], ["1", "4", "3", "2"], ["2", "1", "3",
"4"], ["2", "1", "4", "3"], ["2", "3", "1", "4"], ["2", "3", "4", "1"],
["2", "4", "1", "3"], ["2", "4", "3", "1"], ["3", "1", "2", "4"], ["3",
"1", "4", "2"], ["3", "2", "1", "4"], ["3", "2", "4", "1"], ["3", "4", "1",
"2"], ["3", "4", "2", "1"], ["4", "1", "2", "3"], ["4", "1", "3", "2"],
["4", "2", "1", "3"], ["4", "2", "3", "1"], ["4", "3", "1", "2"], ["4",
"3", "2", "1"]]


 
 Dave Yang  <QuantumWave Interactive - Toronto, Ontario, Canada>

 Email: qwi@astral.magic.ca . Web Page: http://www.magic.ca/~qwi