scion4581 scion4581 - 1 month ago 8
PHP Question

Get all n-size combinations with k-size letters list

Could anyone help me? I am trying find formula and write piece of code in PHP language which makes next

Imagine, we have 3 types of something, k = 1,2,3 and length of this numbers could be various (n-length), but neighboring type should not(!) be the same - 1,1 or 2,2

For example
k = 1,2,3
n = 5

Output
1,2,3,1,2 |
1,2,3,1,3 |
1,2,3,2,1 |
1,2,3,2,3 |

1,3,2,1,3 |
1,3,2,1,2 |
1,3,2,1,3 |
1,3,2,3,1 |
1,3,2,3,2
.........

Mb this is has some common named problem, share with me pls and I'will try to find some resources about

Thanks

MBo MBo
Answer

The simplest way of generation such lists is recursive (if n, k are not large -note that variant count is k*(k-1)n-1).

Pseudocode:

Generate(list, n, k, lastvalue)
    if (list.length = n)
          output(list)
    else
          for i = 1 .. k
              if (i != lastvalue)
                  Generate(list + i, n, k, i)

Delphi code

procedure Generate(list: string; n, k, lastvalue: Integer);
var
  i: Integer;
begin
    if (Length(list) = n) then
          Memo1.Lines.Add(list)
    else
          for i := 1  to k do
              if (i <> lastvalue) then
                  Generate(list + IntToStr(i), n, k, i)
end;

begin
  Generate('', 4, 3, 0);

Output for n=4, k=3

1212  1213  1231  1232  1312  1313  1321  1323  
2121  2123  2131  2132  2312  2313  2321  2323
3121  3123  3131  3132  3212  3213  3231  3232