Generating a powerset of a list where order matters

Question

I was looking for a way to create a powerset of letters basically to generate any possible letter combination but with a twist that order matters so ab != ba. I ran across a nifty bit of code here which I shamelessly pilfered. Here is my entire program:

using System;
using System.Collections.Generic;
using System.Linq;

namespace PermutationsHelper
{
    static class Program
    {
        static void Main()
        {
            var ps = GetPowerSet(new List<string>() { "a", "b" });
            foreach (var item in ps)
            {
                string[] resultArr = item.ToArray();
                string result = string.Join("", resultArr);
                Console.WriteLine(result);
            }
            Console.ReadLine();
        }
        static IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
        {
            return from m in Enumerable.Range(0, 1 << list.Count)
               select
                   from i in Enumerable.Range(0, list.Count)
                   where (m & (1 << i)) != 0
                   select list[i];
        }
    }
}

The output is:

[empty]
a
b
ab

But what I am looking for is:

[empty]
a
b
ab
ba

Any suggestions on how best to accomplish this? TIA

Possible duplicate of [Listing all permutations of a string/integer](https://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer) — Progman, Jun 16 '19 at 10:40
Tried that, the output for the above would be just ab, ba, although perhaps adding a for loop and printing the pieces should work. Wondering if there was a more elegant solution. — ds_practicioner, Jun 16 '19 at 15:36

score 0 · Answer 1 · answered Jun 16 '19 at 16:07

H/T to Progman, here is my solution:

class Program
{
    static List<string> biggestList = new List<string>();

    static void Main(string[] args)
    {
        string str = "abc";
        char[] arr = str.ToCharArray();
        GetPer(arr);
        Console.WriteLine("Complete List:");
        for (int i = 0; i < biggestList.Count; i++)
            Console.WriteLine(biggestList[i]);
        Console.ReadKey();
    }
    private static void Swap(ref char a, ref char b)
    {
        if (a == b) return;

        a ^= b;
        b ^= a;
        a ^= b;
    }

    public static void GetPer(char[] list)
    {
        int x = list.Length - 1;
        GetPer(list, 0, x);
    }

    private static void GetPer(char[] list, int k, int m)
    {
        if (k == m)
        {
            string result = string.Join("", list.ToArray());
            for (int i = 0; i < result.Length; i++)
            {
                if(!biggestList.Contains(result.Substring(0, i + 1)))
                    biggestList.Add(result.Substring(0, i+1));
            }
        }
        else
        {
            for (int i = k; i <= m; i++)
            {
                Swap(ref list[k], ref list[i]);
                GetPer(list, k + 1, m);
                Swap(ref list[k], ref list[i]);
            }
        }
    }
}

score 0 · Accepted Answer · answered Jun 16 '19 at 16:15

You can use the recursive approach as in the answer Listing all permutations of a string/integer to get all possible combinations and permutations, including different orders. You define a method like public static ISet<string> CombinationsAndPermutations(string input) which works as follow:

When the input is empty, return an empty list. (nothing to do)
When the input is a string of length 1, return a Set with the values string.Empty and the input string. (recursion base case)

For all the other cases you iterate over all the characters of the string and find solutions for this specific character or string position. You collect all sub solutions in a total result list and return it. The pseudo code will look like this:

for all positions in the string:
    get the character at position "i"
    get the remaining string without the character at position "i"
    get the solution for the remaining string (recursive call)

    add the solution to a total list of solutions
    add the solution to a total list of solutions, but add the extracted character from position "i" at the front

return the total list

That being said, the solution will look like this:

public static ISet<string> CombinationsAndPermutations(string input) {
    if (string.IsNullOrWhiteSpace(input)) {
        return new HashSet<string>();
    }
    if (input.Length == 1) {
        return new HashSet<string> { string.Empty, input };
    }

    ISet<string> result = new HashSet<string>();
    for (int i=0; i<input.Length; i++) {
        char letter = input[i];
        string remainingBefore = input.Substring(0, i);
        string remainingAfter = input.Substring(i+1);
        string remaining = remainingBefore + remainingAfter;

        ISet<string> subResult = CombinationsAndPermutations(remaining);

        foreach (string subStr in subResult) {
            result.Add(subStr);
            result.Add(letter + subStr);
        }
    }

    return result;
}

For the example input "abc", this will generate a Set with the following entries:

(, a, b, ab, c, ac, bc, abc, cb, acb, ba, bac, ca, bca, cab, cba)

Generating a powerset of a list where order matters

2 Answers2