Little combination problem

Alex Tweedly alex at tweedly.net
Sat May 7 08:57:11 EDT 2005


jbv wrote:

>Hi list,
>
>I'm facing a little combination problem in which I'm getting lost...
>
>I have a string tof n letters (n can range from 2 to 20)
>and I need to produce all possible combinations of n-1 to 2 letters.
>
>for example :
>    string : ABCD
>  
>
>I'm trying to do it with nested loops but don't get anywhere...
>
>Any idea ?
>  
>
I'm sure there's a better way - but here's what I came up with ....

The easy way to do it is recursively :

function allsubstrs str
  put empty into res
  repeat with i = (the number of chars in str)-1 down to 2
    put generate(i,str) after res
  end repeat
  return res
end allsubstrs


function generate M, str
  put the number of chars in str into N
  put empty into res
  if M = 1 then
    repeat for each char c in str
      put c & cr after res
    end repeat
    return res
  end if
  repeat with  i = 1 to N-M+1
    put generate(M-1, char i+1 to -1 of str) into temp
    repeat for each line L in temp
      put char i of str & L & cr after res
    end repeat
  end repeat
  return res
  
end generate

It can be re-written to use loops instead of recursive calls - but it's 
more obvious this way.

-- 
Alex Tweedly       http://www.tweedly.net



-- 
No virus found in this outgoing message.
Checked by AVG Anti-Virus.
Version: 7.0.308 / Virus Database: 266.11.5 - Release Date: 04/05/2005



More information about the use-livecode mailing list