How to generate a sequence of numbers while respecting some constraints?

Question

I need to generate all possible numbers (integers) from 0 to 999999 (without repetition) while respecting a series of constraints.

To better understand the requirements, imagine each number being formed by a 2 digit prefix and a suffix of 4 digits. Like 000000 being read as 00-0000 and 999999 as 99-9999. Now to the rules:

• prefixes must be in random order
• suffixes must be in random order while making sure that each 10k numbers in the sequence have all numbers from 0000 to 9999.
• must be able to generate the numbers again in the same order, given a seed.
• Not really a requirement but it would be great if it was done using Linq.

Thus far, I have written some code that meets all requirements but the first one:

var seed = 102111;
var rnd = new Random(seed);
var prefix = Enumerable.Range(0, 100).OrderBy(p => rnd.Next());
var suffix = Enumerable.Range(0, 10000).OrderBy(s => rnd.Next());
var result = from p in prefix
                from s in suffix
                select p.ToString("d2") + s.ToString("d4");

foreach(var entry in result)
{
    Console.WriteLine(entry);
}

Using this I am able to reproduce the sequence by using the same seed, the first 10000 numbers have all numbers from 0000 to 9999, as does the second 10k and so on, but the prefixes are not really random since each 10k group will have the same prefix.

I also thought of creating a class with the number and it's group (100 groups, each group having 10k numbers) to make it easier to shuffle but I believe that are better, simpler ways to do it.

Answer 1

[I've overwritten an earlier, wrong solution based on a misunderstanding of the problem].

---

We start by making a helper method that produces a shuffled range based on a given seed:

static IEnumerable<int> ShuffledRange(int size, int seed)
{
  var rnd = new Random(seed);
  return Enumerable.Range(0, size).OrderBy(p => rnd.Next());
}

The next thing we're going to do is to randomize all the suffixes and get all of them into a sequence. Note that we use a different seed for each shuffle, but the value of the seed is predictable.

static IEnumerable<string> ShuffledIds(int seed)
{
  const int s = 10000;
  const int p = 100;
  var suffixes = Enumerable.Range(0, p)
    .Select(seedOffset => ShuffledRange(s, seed + seedOffset)
    .SelectMany(x => x);

We've met the constraint that each chunk of 10000 has all 10000 suffixes, in random order. Now we have to distribute 10000 of each prefix. Let's make a sequence of prefixes for each possible suffix. (Again, we use a not-yet-used seed for each shuffle.)

  var dict = new Dictionary<int, IEnumerator<int>>();
  for (int suffix = 0; suffix < s; suffix += 1)
    dict[suffix] = ShuffledRange(p, seed + p + suffix).GetEnumerator();

And now we can distribute them

  foreach(int suffix in suffixes)
  {
    dict[suffix].MoveNext();
    yield return dict[suffix].Current.ToString("d2") +
     suffix.ToString("d4");
  }
}

And that should do it.

Notice that this also has the nice property that the shuffling algorithm is no longer the concern of the code which needs shuffles. Try to encapsulate details like that in helper functions.

Answer 2

Using the idea posted by ckuri and including the imporvements suggested by Eric Lippert, you can group the list of numbers by suffix:

var prefixLength = 100;
var suffixLength = 10000;

 Enumerable
  .Range(0, prefixLength * suffixLength)
  .OrderBy(number => rnd.Next())
  .GroupBy(number => number % suffixLength)

Then, you can flatten the list:

Enumerable
 .Range(0, prefixLength * suffixLength)
 .OrderBy(number => rnd.Next())
 .GroupBy(number => number % suffixLength)
 .SelectMany(g => g)

Until here, you will have a list of numbers, where, in each 100 lines (prefixLength), the prefixes will be the same. So, you can select them, getting the index of each line:

Enumerable
 .Range(0, prefixLength * suffixLength)
 .OrderBy(number => rnd.Next())
 .GroupBy(number => number % suffixLength)
 .SelectMany(g => g)
 .Select((g, index) => new { Index = index, Number = g })

Using the index information, you can group the lines applying the mod function, using the prefixLength as a factor:

Enumerable
 .Range(0, prefixLength * suffixLength)
 .OrderBy(number => rnd.Next())
 .GroupBy(number => number % suffixLength)
 .SelectMany(g => g)
 .Select((g, index) => new { Index = index, Number = g })
 .GroupBy(g => g.Index % prefixLength, g => g.Number)

Finally, you can flatten the list again, and convert the values to string, in order to get the final result:

Enumerable
 .Range(0, prefixLength * suffixLength)
 .OrderBy(number => rnd.Next())
 .GroupBy(number => number % suffixLength)
 .SelectMany(g => g)
 .Select((g, index) => new { Index = index, Number = g })
 .GroupBy(g => g.Index % prefixLength, g => g.Number)
 .SelectMany(g => g)
 .Select(number => $"{number/suffixLength:d2}{number%suffixLength:d4}")