  lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

• Subject: Re: Listing all Permutations using recursive function
• From: Rici Lake <lua@...>
• Date: Tue, 16 Aug 2005 17:05:33 -0500

```
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
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

```
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.
```

```

• References: