Generate subsets of k elements from a set of strings

Question

This is the task:

Write a recursive program, which prints all subsets of a given set of N words.

Example input:

words = {'test', 'rock', 'fun'}

Example output:

(), (test), (rock), (fun), (test rock), (test fun),

(rock fun), (test rock fun)

In fact I need to generate all subsets from 0 to words.Length. In Pascal (if anybody knows) there is a function (not sure that it's "function") that looks like that:

var a:set of example

I need the same in C#. This is what I tried (the program works, but it's a lot of code):

class Program
{
    static int abc;
    static string[] extractedwords;
    static int k;
    static int margin;
    static string[] words = { "coffee", "ice-cream", "chocolate", "red" };
    static void Main(string[] args)
    {
        abc = 0;
        k = 1;
        Console.WriteLine("The margin of words: ");
        margin = int.Parse(Console.ReadLine());
        extractedwords = new string[margin];
        GenerateWords(0);
    }
    static void GenerateWords(int n)
    {
        if (n == k)
        {
            if (n != 0)
            {
                for (int s = n - 1; s >= 0; s--)
                {
                    for (int a = 0; a < s; a++)
                    {
                        if (extractedwords[s] == extractedwords[a])
                        {
                            return;
                        }
                    }
                }
            }
            PrintWords(extractedwords);
            return;
        }
        for (int a = 0; a < words.Length; a++)
        {
            extractedwords[n] = words[a];
            GenerateWords(n + 1);
        }
        if (k >= margin)
        {
            return;
        }
        if (n == 0)
        {
            k++;
            GenerateWords(n);
        }
    }
    static void PrintWords(string[] words)
    {
        for (int n = 0; n < words.Length; n++)
        {
            Console.Write("{0} ", words[n]);
        }
        Console.WriteLine();
    }
}

Answer 1

Unused variables

At least one of your variables (abc) is never used. This might be because you've changed the way the code works. If you refactor your code, try to remember to cleanup at the same time / straight after. It's a lot easier to do while the code is fresh in your mind and it prevents large amounts of technical debt building up over time.

margin of words

I found this prompt confusing (maybe it's just me). I think a better prompt would be something like "Please enter the maximum number of words per group: ". Try to be expressive and imagine that you're not going to be the one using your application.

Variable Names

Similarly, think about your variable names. They should express what it is the variables actually represent. Names like k, s, n and a tell me nothing about what the variable represents. This makes the code harder to read because you have to keep referring back to determine the previous context. Single letter variable names can be ok for short iteration variables where the context is obvious, but can you honestly say that this is meaningful in its current state:

for (int s = n - 1; s >= 0; s--)

Magic Numbers

You've got some magic numbers in your code. I'm not totally against using numbers when the context makes it obvious what the numbers mean. However, this isn't always the case with yours. For example:

GenerateWords(0);

When I look at this line, it looks like the method is going to generate 0 words which doesn't make sense. Looking at the function definition, the parameter is labelled as n, which again adds no context.

Console Output

At the moment your outputting straight to the console as you generate the combinations. Generally, you want to try to separate user interaction from your algorithms. This allows you to reuse the algorithms in different contexts, put different front ends on your code etc.

Static State

At the moment, your storing your state in static variables that are accessed from your recursive method. This is OK in your example code, however if you were to put the method into a library, it would mean that you couldn't call it from two different threads to process different word lists. If the state is passed in, instead, the methods become more flexible.

Minimise what your client needs to know

When you write recursive functions, you'll often need to pass extra parameters into the method in order to support the recursion and the termination conditions. Clients shouldn't need to know this information (this give you more flexibility if you want to change the way the method works in the future).

Putting it together

Putting some of the above together, you might end up with code something like this:

static void Main()
{
    var combinations = GenerateWordCombinations(new string[] { "coffee", "ice-cream", "chocolate", "red" }, 2);

    combinations.ForEach(x => Console.WriteLine($"({x})"));
}

static public List<string> GenerateWordCombinations(string[] inputWords, int? maxWordsPerCombination = null)
{
    var combinations = new List<string> { "" };
    GenerateWordCombinations(inputWords, "", maxWordsPerCombination??inputWords.Length, combinations);
    return combinations;
}

static private void GenerateWordCombinations(IEnumerable<string> words, string prefix, int maxWordsPerCombination, IList<string> combinations)
{
    if(words.Count() == 0 || maxWordsPerCombination == 0)
    {
        return;
    }

    foreach(var word in words)
    {
        GenerateWordCombinations(words.Where(x => x != word), prefix + word + " ", maxWordsPerCombination - 1, combinations);
        combinations.Add(prefix + word);
    }
}

Things to note about the alternative code above:

• I've ignored user input
• There's two versions of GenerateWordCombinations, the private one which is recursive and a public one which can be called from clients. The public one accepts a list of words to search for combinations and the maximum number of words to find in each combination. The number of words is optional and defaults to null, so that if it's not supplied the number of words in the supplied list can be used instead.
• Rather than printing directly to the console, the GenerateWordCombinations methods add the combinations to a list and then returns the list to the caller.
• The code uses some of the collection extension methods to do some of the heavy lifting.
• Combinations are output in a different order from your original application.

Answer 2

Check out these two. Generic. Shorter. However they only give results of a certain length. So in your case you will need a simple loop over each desired length.

    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length) where T : IComparable
    {
        if (length == 1) return list.Select(t => new T[] { t });
        return GetPermutations(list, length - 1).SelectMany(t => list.Where(e => t.All(g => g.CompareTo(e) != 0)), (t1, t2) => t1.Concat(new T[] { t2 }));
    }

    public static IEnumerable<IEnumerable<T>> GetOrderedSubSets<T>(IEnumerable<T> list, int length) where T : IComparable
    {
        if (length == 1) return list.Select(t => new T[] { t });
        return GetOrderedSubSets(list, length - 1).SelectMany(t => list.Where(e => t.All(g => g.CompareTo(e) == -1)), (t1, t2) => t1.Concat(new T[] { t2 }));
    }