Permutations using same letters

Question

I am current working on a project where I need to generate all possible permutations from a given set of characters. I am currently using this code:

public static IEnumerable<string> AllPermutations(this IEnumerable<char> s)
{
    return s.SelectMany(x =>
    {
        var index = Array.IndexOf(s.ToArray(), x);
        return s.Where((y, i) => i != index).AllPermutations().Select(y => new string(new[] { x }.Concat(y).ToArray())).Union(new[] { new string(new[] { x }) });
    }).Distinct();
}

From this answer.

The problem I have is that it won't generate permuations that use the same letter more than once.

For example if I used abcde as the input I need it to generate combinations like aaaaa and dcc etc.

I'm not experienced enough with LINQ to understand where the code is stopping duplicate letters. Any help is greatly appreciated.

I didn't write this, so was just looking for code that did the job really. — Bali C, Mar 09 '12 at 13:54
'aaaaa' is not a permutation of 'abcde'. If your project requires permutations don't include 'aaaaa', if you include 'aaaaa' don't call it a permutation (or a combination for that matter). You'll just confuse everyone reading your question, including yourself. — High Performance Mark, Mar 09 '12 at 13:55
@HighPerformanceMark Yes, I am very confused :) I'm not sure what terminology to use for what I need... — Bali C, Mar 09 '12 at 13:57
Perhaps you want all the 5 letter words from the alphabet 'abcde' ? — High Performance Mark, Mar 09 '12 at 14:00
I also need any shorter versions, from 1 character to the string length, using all the input letters in any order. — Bali C, Mar 09 '12 at 14:03
so it's just a base 5 number system, then just count from 'a' to 'eeeee' — PeskyGnat, Mar 09 '12 at 14:13
@BaliC: Just to be clear, for a given string on length n, all possible variations of length 1 to n including repeated characters? Is order important? In other words do you want both "ab" and "ba"? — Matt Burland, Mar 09 '12 at 14:24
@MattBurland Yeah thats right. If I gave "abc" I would want a, aa, aaa, ab, ba, etc - all combos, thanks. — Bali C, Mar 09 '12 at 14:26

Matt Burland · Accepted Answer · 2012-03-09T16:07:29.840

3

This might work, but I'm sure it could be done more efficiently (taking the counting prompt from PeskyGnat):

    static IEnumerable<string> GetVariations(string s)
    {
        int[] indexes = new int[s.Length];
        StringBuilder sb = new StringBuilder();

        while (IncrementIndexes(indexes, s.Length))
        {
            sb.Clear();
            for (int i = 0; i < indexes.Length; i++)
            {
                if (indexes[i] != 0)
                {
                    sb.Append(s[indexes[i]-1]);
                }
            }
            yield return sb.ToString();
        }
    }

    static bool IncrementIndexes(int[] indexes, int limit)
    {
        for (int i = 0; i < indexes.Length; i++)
        {
            indexes[i]++;
            if (indexes[i] > limit)
            {
                indexes[i] = 1;
            }
            else
            {
                return true;
            }
        }
        return false;
    }

Edit: Changed to use yield return as per Rawlings suggestion. Much better memory usage if you don't need to keep all the results and you can start using the results before they've all been generated.

edited Mar 09 '12 at 16:07

answered Mar 09 '12 at 14:39

Matt Burland

44,552
18
99
171

That is absouletly brilliant! I can't thank you enough. +1 and accept, thanks! – Bali C Mar 09 '12 at 14:48
Whether or not this could be done more efficiently, I'm sure it could be done a lot less efficiently. E.g. my answer :D – Rawling Mar 09 '12 at 14:50
@Rawling: Actually one thing mine doesn't do that your does is deal with duplicates. For example, if the string is "cca", mine will spit out "caa" twice, once for each "c" which it sees as different. Yours doesn't do that. – Matt Burland Mar 09 '12 at 15:03
I couldn't figure out which one to upvote, they both ran out of memory at some point, i.e. with an input string of "abcdefghijk", but work well enough for small cases – PeskyGnat Mar 09 '12 at 15:10
@Pesky There is a way of doing this that uses O(1) space (as long as you don't _keep_ all of the strings you get out) but I'm not capable of remembering it right now. – Rawling Mar 09 '12 at 15:15
@PeskyGnat: No doubt. I only tried it up to about 8 characters which took a few seconds to run. It's a problem that blows up really quickly. – Matt Burland Mar 09 '12 at 15:18
1

@Matt Oh, mine doesn't _intentionally_ deal with duplicates. Yours is in fact the O(1)-space solution I was thinking of, if you just switch to using `yield return` instead of a `List`. Edit: in fact the duplicates thing is trivial, just check the length of the input string, then strip it of duplicate characters before using it as your input... – Rawling Mar 09 '12 at 15:27
1

Yes, the yield would make this handle larger values without any memory overhead, and adhere more closely to the original interface of returning an Enumerable – PeskyGnat Mar 09 '12 at 15:50
@Rawling: Good suggestion on the yield return. I always forget about that feature. – Matt Burland Mar 09 '12 at 16:05

score 3 · Answer 2 · answered Mar 09 '12 at 14:47

I'm amazed this works. It basically goes "make a list of strings from the characters. Then to each string taken from the list, add each character again, and add the resulting strings to the list. Repeat until you've got the right length."

public static IEnumerable<string> BuildStrings(this IEnumerable<char> alphabet)
{
    var strings = alphabet.Select(c => c.ToString());
    for (int i = 1; i < alphabet.Count(); i++)
    {
        strings = strings.Union(strings.SelectMany(s => alphabet.Select(c => s + c.ToString())));
    }
    return strings;
}

Aha, it only works because I'm doing `Union` rather than `Concat`, otherwise I'd have many, many duplicates... — Rawling, Mar 09 '12 at 15:12

score 0 · Answer 3 · answered Mar 09 '12 at 16:03

A funny one using only recursive lambdas via a fixpoint operator (thx @Rawling for the SelectMany)

// Fix point operator   
public static Func<T, TResult> Fix<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> f)
    {
        return t => f(Fix<T, TResult>(f))(t);
    }

And then

var chars = new[] {'a','b','c','d','e'}.Select(c=>c.ToString()) ;

var result = Fix<int,IEnumerable<string>>(
    f => 
      x => 
       x == 1
         ? chars
         : chars.Union(f(x - 1).SelectMany(s => chars.Select(c => s + c))))(chars.Count());

Permutations using same letters

3 Answers3