0

To provide some context: I'm developing an algorithmic question builder where end-users can input variables, assign them ranges and rules, use them in formulas and achieve (x) amounts of questions.

I'm currently needing to populate x amounts of dictionaries of x number of elements with the keys of the variable names [a], [b], [c].. etc etc, with each value being a unique and every possibility of the range they can potentially be; i.e a = 1 - 100, b = 1 - 50 etc etc.

So 1st dict would be:
[a] = 1
[b] = 1
[c] = 1

2nd dict
[a] = 2
[b] = 1
[c] = 1

Is there a simple recursive function that can handle this better than an iterative function?

Thanks for the help!

daniel-schofield93
  • 13
  • 2
  • 2
    Why is an iterative solution not sufficient? – Gerard Sexton Mar 03 '16 at 01:58
  • What you want is the cartesian product of the ranges. There are numerous questions about that on this site; try http://stackoverflow.com/questions/4073713/is-there-a-good-linq-way-to-do-a-cartesian-product/4073806#4073806 to start with. – Eric Lippert Mar 03 '16 at 02:35
  • @GerardSexton no particular reason why it's not sufficient, I just find recursive algorithms to be more efficient and elegant. – daniel-schofield93 Mar 03 '16 at 03:16
  • Thank you for the hint @EricLippert, I will look into that! – daniel-schofield93 Mar 03 '16 at 03:17
  • @GerardSexton - It sounds like to me that the number of variable names is not fixed so a recursive method would be easier to write than an iterative. Pop the head and recurse the tail. – Enigmativity Mar 03 '16 at 03:46

1 Answers1

1

If I start with a structure that can represent your range of values, like this:

public struct Range
{
    public int Minimum { get; set; }
    public int Maximum { get; set; }
}

...then I can represent your inputs like this:

var inputs = new Dictionary<string, Range>()
{
    { "a", new Range() { Minimum = 1, Maximum = 3 } },
    { "b", new Range() { Minimum = 1, Maximum = 2 } },
    { "c", new Range() { Minimum = 1, Maximum = 2 } },
};

...and then I can build the results like this:

Func<IEnumerable<KeyValuePair<string, Range>>, IEnumerable<Dictionary<string, int>>> build = null;
build =
    kvps =>
    {
        if (kvps.Skip(1).Any())
        {
            return
                from kvp in kvps.Take(1)
                from n in Enumerable.Range(kvp.Value.Minimum, kvp.Value.Maximum - kvp.Value.Minimum + 1)
                from r in build(kvps.Skip(1))
                select new[] { new KeyValuePair<string, int>(kvp.Key, n) }.Concat(r).ToDictionary(x => x.Key, x => x.Value);
        }
        else
        {
            return
                from kvp in kvps
                from n in Enumerable.Range(kvp.Value.Minimum, kvp.Value.Maximum - kvp.Value.Minimum + 1)
                select new[] { new KeyValuePair<string, int>(kvp.Key, n) }.ToDictionary(x => x.Key, x => x.Value);
        }
    };

This produces the following list of dictionaries:

a=1, b=1, c=1 
a=1, b=1, c=2 
a=1, b=2, c=1 
a=1, b=2, c=2 
a=2, b=1, c=1 
a=2, b=1, c=2 
a=2, b=2, c=1 
a=2, b=2, c=2 
a=3, b=1, c=1 
a=3, b=1, c=2 
a=3, b=2, c=1 
a=3, b=2, c=2

Here's an explanation of the main query:

from kvp in kvps.Take(1)

Get the first element from the kvps enumerable (this is the "head" of the enumerable)

from n in Enumerable.Range(kvp.Value.Minimum, kvp.Value.Maximum - kvp.Value.Minimum + 1)

Generate all of the values of n from Minimum to Maximum.

from r in build(kvps.Skip(1))

Recursively call build on the "tail" of the list to generate all of the possible tail dictionaries

select new[] { new KeyValuePair<string, int>(kvp.Key, n) }.Concat(r).ToDictionary(x => x.Key, x => x.Value);

Create a new KeyValuePair<string, int>[] with the Key and the value n and concatenate each value from the tail (r) at create a new dictionary.

Enigmativity
  • 113,464
  • 11
  • 89
  • 172