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
– Bali C, Commented Mar 9, 2012 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
– High Performance Mark, Commented Mar 9, 2012 at 13:55
I also need any shorter versions, from 1 character to the string length, using all the input letters in any order. — Bali C
– Bali C, Commented Mar 9, 2012 at 14:03

Matt Burland · Accepted Answer · 2012-03-09 16:07:29Z

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 9, 2012 at 16:07

answered Mar 9, 2012 at 14:39

Matt Burland

45.3k18 gold badges110 silver badges182 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Bali C Over a year ago

That is absouletly brilliant! I can't thank you enough. +1 and accept, thanks!

Rawling Over a year ago

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

Matt Burland Over a year ago

@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.

Rawling Over a year ago

@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...

PeskyGnat Over a year ago

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

|

Rawling · Accepted Answer · 2012-03-09 14:47:59Z

3

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;
}

answered Mar 9, 2012 at 14:47

Rawling

50.3k7 gold badges94 silver badges131 bronze badges

1 Comment

Rawling Over a year ago

Aha, it only works because I'm doing Union rather than Concat, otherwise I'd have many, many duplicates...

jbl · Accepted Answer · 2012-03-09 16:03:33Z

0

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());

answered Mar 9, 2012 at 16:03

jbl

15.5k3 gold badges37 silver badges104 bronze badges

Collectives™ on Stack Overflow

Permutations using same letters

3 Answers 3

9 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

9 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related