How to generate all unique 4 character permutations of a seed string?

Question

Possible Duplicate:
Algorithm to return all combinations of k elements from n
Generate Distinct Combinations PHP

I have an array containing a number of characters/letter,s e.g:

$seed = array('a','b','c','d','e','f',.....,'z','1','2','3',...'9');

I want to get all possible unique 4 character combinations/permutations from the seed, for example:

abcd, azxy, ag12, aaaa, etc

What's the best way to accomplish this?

I have thought about dividing the seed array into 4 letter groups, then go through each group and generate all possible combinations of that group, but that will leave out many combinations (i.e it will process abcd and wxyz, but not abyz and wxcd)

@sehe: they could be permutations of 4-letter subsets of 35 (k-permutations). — ninjagecko, May 01 '12 at 21:46
I don't think this is a duplicate, those questions are about different things than what I'm asking — Ali, May 01 '12 at 21:47
@Click Upvote: just to translate the question.. is `aaaa` a valid output? — Karoly Horvath, May 01 '12 at 21:47
I.e in one question its asking about generating 5 combinations where each combo has 2 digits (so a total of 10 chars with 5 combos each), whereas im asking for 4 character combos, each combo like abcd, adcb, etc — Ali, May 01 '12 at 21:48
@ClickUpvote: Ok, you're looking for permutations, not combinations. But the principle for generating them is very similar. — Oliver Charlesworth, May 01 '12 at 22:04
@OliCharlesworth: He is not looking for permutations nor combinations. He is looking to get all possible combinations-with-replacement, or all elements of the 4th cartesian exponent of the set. He may or may not be considering them as sets or as ordered lists. — ninjagecko, May 01 '12 at 22:57
@ninjagecko No. However I figured this out using my own algorithm :) — Ali, May 02 '12 at 13:43

score 1 · Accepted Answer · edited May 23 '17 at 11:49

1

For each character in the array, write that character followed by each of the unique 3 character strings either from the characters after it (if you actually mean combinations) or from all the characters (which is what I think you mean).

How to generate all unique 3 character permutations of a seed string?

See this very similar question.

You may also want to read about recursion.

Python code

>>> def product(chars, n):
        if n == 0:
            yield ''
        else:
            for c in chars:
                for result in product(x, n - 1):  # Recursive call
                    yield c + result

>>> list(product(['a', 'b', 'c'], 2))
['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']

(Note: in real Python code you should use itertools.product rather than writing it yourself.)

edited May 23 '17 at 11:49

Community

1
1

answered May 01 '12 at 21:43

Mark Byers

811,555
193
1,581
1,452

This doesn't answer my question – Ali May 01 '12 at 21:52
2

@ClickUpvote: If this doesn't answer your question, then you need to clarify your question, because it answers what you've written. – Oliver Charlesworth May 01 '12 at 22:04
@OliCharlesworth How does it answer the question 'how to generate unique permutations' by saying 'generate 3 unique permutations'. May be if he gives a code sample to clarify it, I might understand. – Ali May 01 '12 at 22:31
@ClickUpvote: Because you missed that it implies a recursive solution. – Oliver Charlesworth May 01 '12 at 22:33
@OliCharlesworth I understood that he was trying to be witty/clever but it still doesn't answer my question in the manner its written. – Ali May 01 '12 at 22:35
@ClickUpvote: It's not really that clever, in fact it's quite explicit: to generate length-N permutations, you take each start letter in turn, and concatenate all possible length-(N-1) permutations. This eventually hits a trivial base case. – Oliver Charlesworth May 01 '12 at 22:36
@OliCharlesworth Mate I'm not a computer whom you'll give a string like 'take each letter and concatenate all possible length N permutations` and I'll be able to compute it. How do I get all possible length N permutations? That's my question, if I'd known the answer to that I won't be asking this in the first place. – Ali May 01 '12 at 22:38
@ClickUpvote: With respect, this is a very simple concept, and you have 12k rep, implying that you're not a novice programmer. It sounds like you're vying for someone to just give you the code, which I don't think is going to happen... – Oliver Charlesworth May 01 '12 at 22:41
@OliCharlesworth Sometimes simple concepts are simple when you write them in code but they can be complicated when you write them in english. May be if you post an answer with some code doing what you're saying then I'll be able to figure it out. – Ali May 01 '12 at 22:42
@ClickUpvote: Anyway, as already pointed out, there are plenty of questions on SO already doing something very similar to what you want. At least one of them must give you the relevant insight. – Oliver Charlesworth May 01 '12 at 22:44
2

@ClickUpvote: How do you get all possible length 1 "permutations"? You can do that, right? OK, so now extend that to 2 letters by writing each letter followed by all the length 1 permutations. OK so far? Now extend that to 3 letters by writing each letter followed by all the length 2 permutations. Spot a pattern yet? – Mark Byers May 01 '12 at 22:44

score 0 · Answer 2 · answered May 01 '12 at 22:25

0

Generating permutations is like summing up numbers. This is beautifully explained in the freely available book Higher Order Perl, page 128

answered May 01 '12 at 22:25

jpmuc

1,092
14
30

How to generate all unique 4 character permutations of a seed string?

2 Answers2