### 1. Get combinations of digits in a sequence

Here are 2 recursive functions that give all combinations of digits in a sequence.

```sequence combinations

procedure get_all_combinations(sequence s, sequence used, integer n)
integer lg

lg = length(s)
if n = lg then
combinations = append(combinations, used)
return
end if
n += 1
for d = 1 to length(s[n]) do
get_all_combinations(s, used&s[n][d], n)
end for
end procedure

------------------------------------------------------------------------------

procedure get_unique_combinations(sequence s, sequence used, integer n)
integer lg

lg = length(s)
if n = lg then
combinations = append(combinations, used)
return
end if
n += 1
for d = 1 to length(s[n]) do
if not find(s[n][d], used) then
get_unique_combinations(s, used&s[n][d], n)
end if
end for
end procedure

```

And here is an example of usage:

```constant
SEQ = {{4,8,9}, {1,2,4}, {1,4,5,6}}

combinations = {}
get_all_combinations(SEQ, {}, 0)
pretty_print(1, combinations, {})
puts(1, "\n")

combinations = {}
get_unique_combinations(SEQ, {}, 0)
pretty_print(1, combinations, {})
puts(1, "\n")
```

Here is the result: get_all_combinations allows duplicate digits, get_unique_combinations does not.

```{
{4,1,1},  {4,1,4},  {4,1,5},  {4,1,6},  {4,2,1},  {4,2,4},
{4,2,5},  {4,2,6},  {4,4,1},  {4,4,4},  {4,4,5},  {4,4,6},
{8,1,1},  {8,1,4},  {8,1,5},  {8,1,6},  {8,2,1},  {8,2,4},
{8,2,5},  {8,2,6},  {8,4,1},  {8,4,4},  {8,4,5},  {8,4,6},
{9,1,1},  {9,1,4},  {9,1,5},  {9,1,6},  {9,2,1},  {9,2,4},
{9,2,5},  {9,2,6},  {9,4,1},  {9,4,4},  {9,4,5},  {9,4,6}
}
{
{4,1,5},  {4,1,6},  {4,2,1},  {4,2,5},  {4,2,6},  {8,1,4},
{8,1,5},  {8,1,6},  {8,2,1},  {8,2,4},  {8,2,5},  {8,2,6},
{8,4,1},  {8,4,5},  {8,4,6},  {9,1,4},  {9,1,5},  {9,1,6},
{9,2,1},  {9,2,4},  {9,2,5},  {9,2,6},  {9,4,1},  {9,4,5},
{9,4,6}
}
```

Jean-Marc

### 2. Re: Get combinations of digits in a sequence

I noted that your routines are not task-safe (and certainly not thread-safe) as some other process could reset combinations to {} under your feet.
It is also not the best design to have to remember to reset combinations before each and every call.
I have also just noticed that my versions lack any way to terminate the scan/build part way through, when something suitable is found..

Regards, Pete

### 3. Re: Get combinations of digits in a sequence

I try to understand how to use permute with my sequence which has sub-items of different lengths. It s too much for my old brain. Could you provide an example using my SEQ constant as an input?

Jean-Marc

### 4. Re: Get combinations of digits in a sequence

Here is what I get with permute, which is not what I expect:

```{
{1,2,4},
{1,4,5,6},
{4,8,9}
}
{
{1,4,5,6},
{4,8,9},
{1,2,4}
}
{
{1,2,4},
{4,8,9},
{1,4,5,6}
}
{
{1,4,5,6},
{1,2,4},
{4,8,9}
}
{
{4,8,9},
{1,4,5,6},
{1,2,4}
}
{
{4,8,9},
{1,2,4},
{1,4,5,6}
}
```

Regards, Jean-Marc

### 5. Re: Get combinations of digits in a sequence

jmduro said...

I try to understand how to use permute with my sequence which has sub-items of different lengths. It s too much for my old brain. Could you provide an example using my SEQ constant as an input?

Sorry, I didn't mean permute, I meant the comb function (also on that page), modified for your specific requirements something like this:

```constant SEQ = {{4,8,9}, {1,2,4}, {1,4,5,6}}

function comb(sequence pool, integer unique=0, sequence res={}, integer i=1, sequence chosen={})
if i>length(pool) then  -- got a full set
res = append(res,chosen)
else
-- get all combinations with something from pool[i]
for j=1 to length(pool[i]) do
object pij = pool[i][j]
if not unique or not find(pij,chosen) then
res = comb(pool,unique,res,i+1,append(chosen,pij))
end if
end for
end if
return res
end function
?comb(SEQ)
?comb(SEQ,1)
```

Same results as your code, but with the initialisation to {} now automated, and an accidental reset by a second task/thread mid-way through now completely impossible.

Lengthy searches through some huge number of combinations are precisely the sort of thing that gets shunted off to a background task/thread, and therefore it is important to ensure they cannot tread on each others toes.

Otherwise, this code is very similar to what you posted.

An alternative that allows early termination:

```constant SEQ = {{4,8,9}, {1,2,4}, {1,4,5,6}}

function comb(sequence pool, integer rid, integer unique=0, integer i=1, sequence chosen={})
if i>length(pool) then  -- got a full set
if not call_func(rid,{chosen}) then return 0 end if
else
-- get all combinations with something from pool[i]
for j=1 to length(pool[i]) do
object pij = pool[i][j]
if not unique or not find(pij,chosen) then
if not comb(pool,rid,unique,i+1,append(chosen,pij)) then return 0 end if
end if
end for
end if
return 1    -- carry on
end function

function test(sequence s)
?s
if equal(s,{4,1,6}) then return 0 end if
return 1    -- carry on
end function

?comb(SEQ,routine_id("test"))   -- {4,1,1} {4,1,4} {4,1,5} {4,1,6}
?comb(SEQ,routine_id("test"),1) -- {4,1,5} {4,1,6}
```

Pete

### 6. Re: Get combinations of digits in a sequence

Thank you Pete,

I'm trying to build my own Kakuro grids. I already can, but they are difficult to resolve, so I try to use different algorithms to build resolvable Kakuro grids.

Regards, Jean-Marc