如何在遵守某些约束的同时生成数字序列？

Question

我需要生成从 0 到 999999（不重复）的所有可能数字（整数），同时遵守一系列约束。

为了更好地理解要求，假设每个号码都由一个 2 位前缀和一个 4 位后缀组成。就像 000000 被读作 00-0000 和 999999 被读作 99-9999。现在进入规则：

前缀必须随机排列
后缀必须随机排列，同时确保序列中的每 10k 个数字都包含从 0000 到 9999 的所有数字。
必须能够以相同的顺序再次生成数字，给定一个种子。
不是真正的要求，但如果使用 Linq 完成就更好了。

到目前为止，我已经编写了一些满足所有要求的代码，但第一个：

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);
}

使用这个我可以使用相同的种子重现序列，前 10000 个数字的所有数字都从 0000 到 9999，第二个 10k 等等，但前缀并不是真正随机的，因为每个10k 组将具有相同的前缀。

我还考虑过用数字和它的组（100 组，每组有 10k 个数字）创建一个 class 以便更容易洗牌，但我相信这是更好、更简单的方法.

Answer 1

[基于对问题的误解，我已经覆盖了一个较早的错误解决方案]。

我们首先制作一个辅助方法，该方法根据给定的种子生成随机范围：

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

接下来我们要做的是随机化所有后缀并将它们全部放入一个序列中。请注意，我们为每次洗牌使用不同的种子，但种子的值是可以预测的。

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);

我们已经满足了 10000 块中的每个块都具有所有 10000 个后缀的约束，顺序是随机的。现在我们必须分配每个前缀 10000 个。让我们为每个可能的后缀制作一系列前缀。（同样，我们为每次洗牌使用一个尚未使用的种子。）

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

现在我们可以分发它们了

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

这样就可以了。

请注意，这也有好处属性洗牌算法不再是需要洗牌的代码的关注点。尝试在辅助函数中封装类似的细节。

Answer 2

使用 and including the imporvements suggested by 发表的想法，您可以按后缀对数字列表进行分组：

var prefixLength = 100;
var suffixLength = 10000;

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

然后，您可以展平列表：

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

到这里为止，您将得到一个数字列表，其中，在每 100 行 (prefixLength) 中，前缀将相同。所以，你可以 select 它们，得到每一行的索引：

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

使用索引信息，您可以对应用 mod 函数的行进行分组，使用 prefixLength 作为一个因子：

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)

最后，您可以再次将列表展平，并将值转换为字符串，以获得最终结果：

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}")

Answer 3

此解决方案受到 Rodolfo Santos 的启发 . It improves over his solution by shuffling the numbers inside each group that share the same suffix, completing the randomness of the resulting sequence. The algorithm takes advantage of the fact that LINQ's OrderBy 排序是稳定的，因此按前缀对数字进行排序不会破坏先前的随机顺序。如果不是这种情况，则需要额外的分组和展平。

public static IEnumerable<int> RandomConstrainedSequence(
    int prefixLength, int suffixLength, int seed)
{
    var random = new Random(seed);
    return Enumerable
    .Range(0, prefixLength * suffixLength)
    .OrderBy(_ => random.Next()) // Order by random
    .OrderBy(n => n / suffixLength) // Order by prefix (randomness is preserved)
    .Select((n, i) => (n, i)) // Store the index
    .GroupBy(p => p.n % suffixLength) // Group by suffix
    // Suffle the numbers inside each group, and zip with the unsuffled stored indexes
    .Select(g => g.OrderBy(_ => random.Next()).Zip(g, (x, y) => (x.n, y.i)))
    .SelectMany(g => g) // Flatten the sequence
    .OrderBy(p => p.i) // Order by the stored index
    .Select(p => p.n); // Discard the index and return the number
}

用法示例：

int index = 0;
foreach (var number in RandomConstrainedSequence(5, 10, 0))
{
    Console.Write($"{number:00}, ");
    if (++index % 10 == 0) Console.WriteLine();
}

输出：

44, 49, 47, 13, 15, 00, 02, 01, 16, 48,
25, 30, 29, 41, 43, 32, 38, 46, 04, 17,
23, 19, 35, 28, 07, 34, 20, 31, 26, 12,
36, 10, 22, 08, 27, 21, 24, 45, 39, 33,
42, 18, 09, 03, 06, 37, 40, 11, 05, 14,

更新： 此解决方案可以推广以解决更大范围的问题，其中排序被限制在序列的每个子组中。这是一个完全可以做到这一点的扩展方法：

public static IEnumerable<TSource> OrderGroupsBy<TSource, TGroupKey, TOrderKey>(
    this IEnumerable<TSource> source,
    Func<TSource, TGroupKey> groupByKeySelector,
    Func<TSource, TOrderKey> orderByKeySelector)
{
    return source
        .Select((x, i) => (Item: x, Index: i))
        .GroupBy(e => groupByKeySelector(e.Item))
        .Select(group =>
        {
            var itemsOrdered = group.Select(e => e.Item).OrderBy(orderByKeySelector);
            var indexesUnordered = group.Select(e => e.Index);
            return itemsOrdered.Zip(indexesUnordered, (x, i) => (Item: x, Index: i));
        })
        .SelectMany(group => group)
        .OrderBy(pair => pair.Index)
        .Select(pair => pair.Item);
}

这个方法的效果可以通过不同的例子更清楚的看出。名称数组是有序的，但顺序被限制在以相同字母开头的名称的每个子组内：

var source = new string[] { "Ariel", "Billy", "Bryan", "Anton", "Alexa", "Barby" };
Console.WriteLine($"Source: {String.Join(", ", source)}");
var result = source.OrderGroupsBy(s => s.Substring(0, 1), e => e);
Console.WriteLine($"Result: {String.Join(", ", result)}");

Source: Ariel, Billy, Bryan, Anton, Alexa, Barby
Result: Alexa, Barby, Billy, Anton, Ariel, Bryan

使用这个扩展方法，原来的问题可以这样解决：

public static IEnumerable<int> RandomConstrainedSequence(
    int prefixLength, int suffixLength, int seed)
{
    var random = new Random(seed);
    return Enumerable
        .Range(0, prefixLength * suffixLength)
        .OrderBy(_ => random.Next()) // Order by random
        .OrderBy(n => n / suffixLength) // Order again by prefix
        // Suffle each subgroup of numbers sharing the same suffix
        .OrderGroupsBy(n => n % suffixLength, _ => random.Next());
}

如何在遵守某些约束的同时生成数字序列？

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

c#

linq

algorithm

combinatorics