Re: Listing all Permutations using recursive function

[Rici Lake <lua@...>]

On 16-Aug-05, at 3:05 PM, Szilard wrote:

(This program was mangled in the mail; I tried to clean it up)

> A={}
> function Combinations(n,m)
>   for i = 1, n do
>     A[m] = i
>     if (m<n) then
>       Combinations(n,m+1)
>     else
>       B=A[1]
>       for j=2,n do
>         B=B ..", ".. A[j]
>       end
>       print(B)
>     end
>   end
> end
> Combinations(4,1)

You would have been better off to have said

  local B = A[1]

since B is clearly a local temporary variable, but even better would be 
to make use of the standard library:

  else
    print(table.concat(A, ', '))
  end

As a little note about optimization, in case you wanted to go beyond 4 
elements, the program spends a significant amount of its time 
repeatedly converting integers to strings in order to concatenate them.

Here's a slightly rewritten version, which shows how Lua's scoping 
rules work:

function Combinations(n)
  local a, vals = {}, {}
  for i = 1, n do
    vals[i] = tostring(i)
  end

  local function aux(m)
    for i = 1, n do
      a[m] = vals[i]
      if m < n then
        aux(m + 1)
      else
        print(table.concat(a))
      end
    end
  end

  aux(1)
end

I know that wasn't what you were asking, but I couldn't resist.


> How can I solve the similar problem when I need only the permutations?

There's a nice example in Programming in Lua, page 73 (available at 
<http://www.lua.org/pil/9.3.html>

The example goes on to demonstrate some interesting features of Lua: 
coroutines and generator functions.