2

I have a list of items and will insert them into a dictionary but must determine keys. For my purposes, the characters that these keys consist of is in the following array: 

char[] keyChars = { '0', '1', 'A', 'B' };

Keys can be varying length.
For example, if length is 2, the first key would be 00 and the last would be BB (assuming I need all of them, probably not in most cases).

However, I'm not sure if I've fried my brain or what, but I cannot figure out how to generate this range of keys.

I have the following skeleton build but haven't been able to figure out what to put in it... 

//These below 2 are determined at runtime and may vary (hardcoded for example's sake)
int count = 8; // Number of keys I need to generate
int length = 3; //Length the key need to be

char[] keyChars = { '0', '1', 'A', 'B' };  

List<string> keys = new List<string>();
char[] result;
for (int i = 0; i < count; i++)
{
    result = new char[length];

    for (int j = length - 1; j >= 0; j--)
    {
        result[j] = keyChars[/*what should go here?*/];
    }

    keys.Add(new string(result));
}

The only thing I'm fairly certain I need is a <something> % keyChars.Length so that I can stay in bounds of the array. But my math knowledge is proving a little rusty at the moment and it's taking me far longer than it should..

Broots Waymb
  • 4,713
  • 3
  • 28
  • 51
  • 1
    So in other words, you're trying to generate all combinations of keys using those characters. – Jeff Mercado Sep 01 '16 at 17:09
  • Are you saying that you should end up with `Math.Pow(keyChars.Length, length)` total keys? Or is it like if length is 2 you get 00, 11, AA, BB? – itsme86 Sep 01 '16 at 17:09
  • You're looking to generate *combinations* of a set. More specifically, combinations of fixed length. (p.s *Danger zooone!!*) – SimpleVar Sep 01 '16 at 17:09
  • Looks like you need [permutations](http://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer). – Olivier Jacot-Descombes Sep 01 '16 at 17:09
  • @JeffMercado - Correct. With the exception that I only need up to a certain number. Of course, I could always get all, then grab a subset, but it seems like a waste. – Broots Waymb Sep 01 '16 at 17:11
  • @OlivierJacot-Descombes Permutation takes each element only once. Slightly different than "combinations" – SimpleVar Sep 01 '16 at 17:11
  • @SimpleVar is correct. I can repeat chars. But each key would be unique (hence being key for a `Dictionary`) – Broots Waymb Sep 01 '16 at 17:13
  • @itsme86 - I would end up with `count` number of keys. So I may not *actually* end up using all the way to BB. The length is independent of how many keys I need to get. Length is just used elsewhere in my program (Think fixed width output file, or database column). – Broots Waymb Sep 01 '16 at 17:16
  • 2
    @DangerZone Translate the problem to something familiar. What you want to do is essentially count in a certain base. Its similar to a clock: count seconds 0-59, into minutes 0-59. That clock has 2 hands, so your combinations are of size 2. For 4 elements, you simply count in base 4 instead of base 60. For combinations of size 3, your clock has 3 hands. – SimpleVar Sep 01 '16 at 17:19
  • See [Combinations With Repetitions C#](http://stackoverflow.com/questions/25824376/combinations-with-repetitions-c-sharp). The solution uses `yield return`, i.e. you can retrieve only a limited number of values. You also would have to add an outer loop that would create an iteration of increasing lengths starting with 1. – Olivier Jacot-Descombes Sep 01 '16 at 17:26
  • @OlivierJacot-Descombes What do you mean that I can only retrieve a limited number of values? And I wouldn't need the outer loop. The length is fixed. If I set it to 3, I do not want 1- and 2-lengthed strings. (assuming I understand your comment correctly). – Broots Waymb Sep 01 '16 at 17:29
  • 1
    By a limited number of values I mean that `IEnumerable`s (and that's what `yield return` creates) are evaluated lazily. I.e., even if the algorithm can yield 1 mio keys, if you need 20, then only 20 will be generated! Of course the outer loop is not needed, if the length is constant. I just imagined that you would want to increase the length of the key dynamically until you get enough keys. – Olivier Jacot-Descombes Sep 01 '16 at 17:38
  • @OlivierJacot-Descombes Thanks. Never used `yield` before. Is there a way to only generate, say, 20 keys with that method? It looks like it will always generate every combination (which would be unnecessary if I only want a few and considering the list of chars I'm using will likely expand to all alphanumerics). – Broots Waymb Sep 01 '16 at 17:41
  • @DangerZone: It's lazy evaluated. It will generate exactly as many keys as you ask it for and no more. If you something like `foreach(var s in CombinationsWithRepition(...)` and after `20` iterations you just *stop*, then it will stop. That's how `yield return` works. – Matt Burland Sep 01 '16 at 17:45
  • `yield return` does not exit the method, instead it pauses it and resumes at the next statement when the next values is fetched. See Jon Skeet's article ["Iterators, iterator blocks and data pipelines"](http://csharpindepth.com/Articles/Chapter11/StreamingAndIterators.aspx) – Olivier Jacot-Descombes Sep 01 '16 at 17:48
  • The yield makes it "put aside" it's execution state, return a single result out of many, and when you ask for the next result it will continue from where it left off, to return the next result. Works similarly (in concept) to a DataReader, where you have the current value and a MoveNext method. This subject is called Iterators in C#. – SimpleVar Sep 01 '16 at 17:48
  • @SimpleVar - So how would I exit (after 20 keys for example) if all yield return does is resume where it left off? It seems like it will always try to keep finding the next combination, so I'm not quite sure how to just stop it and say "ok, thats enough keys now" – Broots Waymb Sep 01 '16 at 17:52
  • 1
    `int i = 0; foreach (x in GetCombinations()) { DoSomethingWith(x); if (++i == 20) break; }` All the rest happens automatically by the magic of `yield return` used in `GetCombinations()`! – Olivier Jacot-Descombes Sep 01 '16 at 17:57
  • Read about C# iterators. It's not directly relevant to the question, just an approach for lazy evaluation, a mechanism that C# provides. After your read, a new question is the proper place to seek help. – SimpleVar Sep 01 '16 at 18:01
  • @OlivierJacot-Descombes I've tried that with no luck. I declared i between the 2 foreach loops and placed the if and break in the inner loop. Still gets me all items rather than 20. – Broots Waymb Sep 01 '16 at 18:03
  • 1
    You must make a difference between writing the algorithm potentially generating all the combinations (without limits) and consuming its result with a single (non-nested) loop with a limit. The limit of 20 goes where you consume, not where you generate the sequence. You can also use the extension method `Take`: `foreach (string s in GetCombinations().Take(20)) { ... }`. this will really only generated 20 keys. Debug and you will see! – Olivier Jacot-Descombes Sep 01 '16 at 18:11
  • Also see http://stackoverflow.com/questions/38923376/return-a-new-string-that-sorts-between-two-given-strings/ – m69's been on strike for years Sep 01 '16 at 18:25

0 Answers0