Permutations with repetition

Question

If you can find a better title, please edit.

I will start by saying I've looked at several q&a's on this topic, mainly this one and this article without having found a way to do this:

Given the word "HALLOWEEN" I would like to find all permutations and combinations for all lengths. The first thing I tried was iterating through the below code giving it length of 1 to begin with and continuing until reaching the length of the word (9).

public static IEnumerable<IEnumerable<T>>
        GetPermutations<T>(IEnumerable<T> list, int length)
    {
        if (length == 1) return list.Select(t => new T[] {t});

        return GetPermutations(list, length - 1)
            .SelectMany(t => list.Where(e => !t.Contains(e)),
                (t1, t2) => t1.Concat(new T[] {t2}));
    }

This gave me unexpected results as the double 'E' and 'L's were omitted, leaving the final set short.

A simpler example could be 'MOM' {M,O,M} where the final set of outcomes would be:

• M

• O

• MO

• OM

• MM

• MOM

• MMO

• OMM

Notice that I want to see both 'M's as available, but I don't want to see "MMM" as a result. "MOM" would appear twice in the result due to leaving original order (1,2,3) and swapping positions 1 and 3 (3,2,1) would both result in 'M','O','M' but this character sequence only appears once is the result list (which can be done by a string comparison)

Again, with set {1,1,2,3} I would expect to see:

{1,1}

but NOT {2,2} or {3,3}

Answer 1

Here's another solution that should be clear and easily understandable:

    public static IEnumerable<string> GetPermutations(string input)
    {
        if (string.IsNullOrEmpty(input))
        {
            return new List<string>();
        }

        var length = input.Length;
        var indices = Enumerable.Range(0, length).ToList();
        var permutationsOfIndices = GetNumericalPermutations(indices, length);

        var permutationsOfInput = permutationsOfIndices.Select(x => new string(x.Select(y => input[y]).ToArray()))
                                                       .Distinct();
        return permutationsOfInput;
    }


    private static List<List<int>> GetNumericalPermutations(List<int> values, int maxLength)
    {
        if (maxLength == 1)
        {
            return values.Select(x => new List<int>{x}).ToList();
        }
        else
        {
            var permutations = GetNumericalPermutations(values, maxLength - 1);

            foreach (var index in values)
            {
                var newPermutations = permutations.Where(x => !x.Contains(index))
                                                  .Select(x => x.Concat(new List<int> { index }))
                                                  .Where(x => !permutations.Any(y => y.SequenceEqual(x)))
                                                  .Select(x => x.ToList())
                                                  .ToList();

                permutations.AddRange(newPermutations);
            }
            return permutations;
        }
    }

For example, the output for "MOM" is:

M
O
OM
MM
MO
MMO
OMM
MOM

Answer 2

I suggest looking at the permutations of the letter positions 0,1,2,3,4,etc mapping those to letters, and then eliminating the duplicates.

Without changing the GetPermutations function, I added another function to get the permutations of the letter positions, map those result to character strings and then eliminate the duplicates.

public void PermutationsTestMethod()
{
    GetPermutationsOfString("MOM").ForEach(v => Debug.Print(v));
}

public List<string> GetPermutationsOfString(string value)
{
    var resultList = new List<string>();

    for (var i = 1; i <= value.Length; i++)
    {
        var permutations = GetPermutations(Enumerable.Range(0, value.Length), i);

        resultList.AddRange(
            permutations
                .Select(v => new string(v.Select(z => value[z]).ToArray()))
                .Distinct()
            );
    }

    return resultList;
}

public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
{
    if (length == 1) return list.Select(t => new T[] { t });

    return GetPermutations(list, length - 1)
        .SelectMany(t => list.Where(e => !t.Contains(e)),
            (t1, t2) => t1.Concat(new T[] { t2 }));
}

Answer 3

This works fine:

Func<string, IEnumerable<string>> getAllSubsets = null;
getAllSubsets = x =>
    (x == null || !x.Any())
        ? Enumerable.Empty<string>()
        :  (x.Length > 1
            ? getAllSubsets(x.Substring(1))
                .SelectMany(y => new [] { y, x.Substring(0, 1) + y })
            : new [] { "", x.Substring(0, 1) });

So given getAllSubsets("ABC") I get:

"", "A", "B", "AB", "C", "AC", "BC", "ABC"

And, for your "MOM" example I get:

"", "M", "O", "MO", "M", "MM", "OM", "MOM"

It would be trivial to filter out the empty string and duplicate values if need be, but as it stands it strictly produces all subsets.

Answer 4

I think it is generally better try to avoid generating and eliminating permutations. Text like "aaaaaaaaaaaaaaab" can generate really big amount of duplications.

public static IEnumerable<IEnumerable<T>>
GetPermutationsInner<T>(IEnumerable<IGrouping<T, T>> groupedList, int length)
{
    if (length == 1) return groupedList.Select(t => new T[] { t.Key });

    return GetPermutationsInner<T>(groupedList, length - 1)
        .SelectMany(t => groupedList
                .Where(e => t.Count(w => w.Equals(e.Key)) < e.Count())
                .Select(s => s.Key),
            (t1, t2) => t1.Concat(new T[] { t2 }));
}

public static IEnumerable<IEnumerable<T>>
    GetPermutations<T>(IEnumerable<T> list)
{
    var resultList = new List<IEnumerable<T>>();
    for (int i = 1; i <= list.Count(); ++i)
    {
        resultList.AddRange(GetPermutationsInner<T>(list.GroupBy(g => g), i));
    }
    return resultList;
}