scion4581 - 10 months ago 51

PHP Question

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

Answer Source

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