-
Feb 13th, 2009, 08:15 PM
#1
Thread Starter
Hyperactive Member
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
-
Feb 13th, 2009, 10:55 PM
#2
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.
-
Feb 14th, 2009, 09:08 AM
#3
Thread Starter
Hyperactive Member
Re: Generating All Permutations with repetition?
Thank's alooot. thats what I need exactly
nice work bro
-
Feb 14th, 2009, 09:18 PM
#4
Re: Generating All Permutations with repetition?
Please set this thread to resolved to let others know.
My usual boring signature: Something
-
Jan 27th, 2016, 01:21 PM
#5
Registered User
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
-
Jan 27th, 2016, 03:34 PM
#6
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.
-
Jan 27th, 2016, 04:04 PM
#7
Registered User
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|