Generating All Permutations with repetition?

Hello
I need a code to do Permutation with repetition for a char array.
Ex:
If I a have char[] = {"a","b"}
The Permutation for 2 letters:
aa
ab
ba
bb
For 3 letters:
aaa
aab
aba
abb
bbb
bba
bab
baa

Thank's alot

I was going to take some time to rewrite this function into something that would use arrays instead of strings, but I've been a bit busy, and this should work for you anyway.

PHP Code:

---

<? 
function permutations($letters,$num){ 
    $last = str_repeat($letters{0},$num); 
    $result = array(); 
    while($last != str_repeat(lastchar($letters),$num)){ 
        $result[] = $last; 
        $last = char_add($letters,$last,$num-1); 
    } 
    $result[] = $last; 
    return $result; 
} 
function char_add($digits,$string,$char){ 
    if($string{$char} <> lastchar($digits)){ 
        $string{$char} = $digits{strpos($digits,$string{$char})+1}; 
        return $string; 
    }else{ 
        $string = changeall($string,$digits{0},$char); 
        return char_add($digits,$string,$char-1); 
    } 
} 
function lastchar($string){ 
    return $string{strlen($string)-1}; 
} 
function changeall($string,$char,$start = 0,$end = 0){ 
    if($end == 0) $end = strlen($string)-1; 
    for($i=$start;$i<=$end;$i++){ 
        $string{$i} = $char; 
    } 
    return $string; 
} 
?>

---

to use:

PHP Code:

---

<? 
$Array=permutations("ABC",3); 
for($i=0 ; $i < count($Array) ; $i++) { 
        echo "$i." . $Array[$i] . "<BR>"; 
} 
?>

---

output:

Code:

---

0.AAA
1.AAB
2.AAC
3.ABA
4.ABB
5.ABC
6.ACA
7.ACB
8.ACC
9.BAA
10.BAB
11.BAC
12.BBA
13.BBB
14.BBC
15.BCA
16.BCB
17.BCC
18.CAA
19.CAB
20.CAC
21.CBA
22.CBB
23.CBC
24.CCA
25.CCB
26.CCC

---

found here.

Thank's alooot. thats what I need exactly :)
nice work bro ;)

Please set this thread to resolved to let others know. :wave:

Hi

Thankyou for this. I spent nearly 4 hours online looking for just this.
However, i observed that the function freezes if i give more than 29 types to choose from.

e.g.
This will work:
$Array=permutations("ABCDEFGHIJKLMNOPQRSTUVWXYZ234",4);
This will NOT:
$Array=permutations("ABCDEFGHIJKLMNOPQRSTUVWXYZ2345",4);

Also, is there a way to simply get the n-th position of a permutation (with repetitions)?
i.e. WITHOUT calculating all possible permutations, so its not inefficient.

e.g.
$Array=permutations("ABCDEFGHIJKLMNOPQRSTUVWXYZ234",4,707280);
should give result: 4444

I don't know PHP, but it seems it should simply come down to a Base X type calculation, so each column would represent a digit of the base raised to a power (the power based on the column number).
You have Base 29 (29 "digits" in your numbering system, A to Z, 2 to 4) (indexes 0 to 28 in your array of digits, i.e. characters)
So, the rightmost column has a value of 29^0, which is 1.
2nd Col 29^1, which is 29
3rd Col 29^2, which is 841
4th Col. 29^3, which is 24389

So, if you take 707280 and divide by 24389 you get 28 with 24388 remainder, so your most significant column is the 28th digit (i.e. character) in your base, which is "4"
Divide 24388 by 841, you'll get 28 again, with a remainder 840, so next column is "4"
Divide 840 by 29, you'll get 28 again, with a remainder of 28, so the next column is "4" and your last column is "4"

wow thats pretty straight forward and very simply put
Thanks a ton for your input
I'm going to try make a php script of it