How to recombine strings

Date: Wed Jul 29 08:40:29 MST 1998
From: Glenn M. Picher <gpicher@MAINE.COM>
Subject: How to recombine strings

>I have five food items (e.g., "Pizza", "Chinese", "Sausages",
>"Mystery", and "Quiche") that I need to recombine in every possible order
>in which none of them is repeated.
Here's two ways to accomplish what you want. One is fast and fairly easy to understand, but utterly tied to the details of your task. The other way is slower to run, a little harder to penetrate, but is generalizable to all such problems, and is really more elegant.

Here's the straightforwared, hard-coded solution. Substitute the "Pizza", "Quiche", etc. strings for "a", "b", etc. in the list on the first line of the handler. 

on uniqueOrders
  set theItems = ["a", "b", "c", "d",  "e"]
  set theAnswer = []
  repeat with i1 = 1 to 5
    repeat with i2 = 1 to 5
      if i1 = i2 then next repeat
      repeat with i3 = 1 to 5
        if i1 = i3 then next repeat
        if i2 = i3 then next repeat
        repeat with i4 = 1 to 5
          if i1 = i4 then next repeat
          if i2 = i4 then next repeat
          if i3 = i4 then next repeat
          repeat with i5 = 1 to 5
            if i1 = i5 then next repeat
            if i2 = i5 then next repeat
            if i3 = i5 then next repeat
            if i4 = i5 then next repeat

            --Unique value has been found. The following lines use at the end
            --the option-return line continuation character  &#172; 
            -- (for clarity, if this character doesn't survive your emailer)

            add theAnswer, &#172;
              [ &#172;
              getAt(theItems, i1), &#172;
              getAt(theItems, i2), &#172;
              getAt(theItems, i3), &#172;
              getAt(theItems, i4), &#172;
              getAt(theItems, i5)  &#172;
              ]
          end repeat
        end repeat
      end repeat
    end repeat
  end repeat
  return theAnswer
end
Test it in the message window with ... 
  put uniqueOrders() into uniqueAnswer
  put count(uniqueAnswer)
  -- 120
Be careful about putting a string version of the returned list into a text castmember, because it may exceed the 32K limit.

Here's the second solution. It uses the programming technique called "recursion", where you solve part of a problem and pass the rest of the problem on to another copy of yourself. Since I'm always harping about people not using recursion appropriately, I thought it was a good opportunity to show an example here. Recursion allows a generic solution for any size list of values you can provide. 

global allOrders, thisOrder

on recurseUniqueOrders theList
  set theCount = count(theList)
  getAllOrders(theCount)
  put count(allOrders) into uniqueCount
  set theAnswer to []
  repeat with i = 1 to uniqueCount
    set thisOrder to getAt(allOrders, i)
    set thisOne = []
    repeat with j = 1 to theCount
      add thisOne, getAt(theList, getAt(thisOrder, j))
    end repeat
    add theAnswer, thisOne
  end repeat
  return theAnswer
end

on getAllOrders valueCount
  set allOrders to []
  set thisOrder to []
  recurseOrders(valueCount, 1)
  return allOrders
end

on recurseOrders valueCount, itemPosition
  if valueCount = itemPosition then
    --last value to set; we're done recursing
    repeat with i = 1 to valueCount
      setAt(thisOrder, valueCount, i)
      if isUnique(thisOrder) then add allOrders, value(string(thisOrder))
    end repeat
  else
    --use recursion to set more values
    repeat with i = 1 to valueCount
      setAt(thisOrder, itemPosition, i)
      recurseOrders(valueCount, itemPosition+1)
    end repeat
  end if
end

on isUnique theList
  set theCount to count(theList)
  if theCount < 2 then return true --done recursing
  set firstValue = getAt(theList, 1)
  repeat with i = 2 to theCount
    if firstValue = getAt(theList, i) then return false
  end repeat
  if theCount = 2 then return true --done recursing
  --use recursion to continue solving the problem
  set newList = value(string(theList))
  deleteAt newList, 1
  return isUnique(newList)
end
Test it in the message window with ... 
  put recurseUniqueOrders(["a","b","c","d", "e"]) into uniqueAnswer
  put count(uniqueAnswer)
  -- 120
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 ...