Results 1 to 7 of 7

Thread: Generating All Permutations with repetition?

  1. #1

    Thread Starter
    Hyperactive Member
    Join Date
    Jun 2005
    Posts
    265

    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

  2. #2
    PowerPoster
    Join Date
    Sep 2003
    Location
    Edmonton, AB, Canada
    Posts
    2,629

    Re: Generating All Permutations with repetition?

    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.

  3. #3

    Thread Starter
    Hyperactive Member
    Join Date
    Jun 2005
    Posts
    265

    Re: Generating All Permutations with repetition?

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

  4. #4
    WiggleWiggle dclamp's Avatar
    Join Date
    Aug 2006
    Posts
    3,527

    Re: Generating All Permutations with repetition?

    Please set this thread to resolved to let others know.
    My usual boring signature: Something

  5. #5
    Registered User
    Join Date
    Oct 2014
    Posts
    5

    Re: Generating All Permutations with repetition?

    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

  6. #6
    Sinecure devotee
    Join Date
    Aug 2013
    Location
    Southern Tier NY
    Posts
    6,582

    Re: Generating All Permutations with repetition?

    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"
    Last edited by passel; Jan 28th, 2016 at 11:15 AM.

  7. #7
    Registered User
    Join Date
    Oct 2014
    Posts
    5

    Re: Generating All Permutations with repetition?

    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

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width