计算第N个排列步骤？

Question

我有一个由小写字母a-z组成的char[26]，通过嵌套的for循环语句，我正在生成一系列序列，例如：

aaa, aaz... aba, abb, abz, ... zzy, zzz.

目前，该软件编写成生成aaa-zzz的所有可能值列表，然后维护一个索引，并对每个值执行操作。

这个列表显然很大，虽然不是非常大，但已经到了内存占用过大的地步（还有其他方面正在被研究，但这是其中之一）。

我正在尝试制定一个公式，可以保留索引，但取消序列列表，并根据当前索引计算当前序列（因为序列之间的操作时间很长）。

例如：

char[] characters = {a, b, c... z};
int currentIndex = 29; // abd

public string CurrentSequence(int currentIndex)
{
    int ndx1 = getIndex1(currentIndex); // = 0
    int ndx2 = getIndex2(currentIndex); // = 1
    int ndx3 = getIndex3(currentIndex); // = 3

    return string.Format(
        "{0}{1}{2}", 
        characters[ndx1], 
        characters[ndx2], 
        characters[ndx3]); // abd
}

我尝试使用子集(abc)来进行小例子的练习，并尝试使用模除法进行索引，但今天我的思路不太清晰，我束手无策。

我不是在寻求答案，只是需要任何形式的帮助。也许是给我指明正确方向的一脚？

- Steven Evers

---

char[25] 不足以容纳 a..z。您可能需要检查缓冲区溢出或其他问题。 - recursive

你究竟想要实现什么？ - second

看起来你正在尝试计算排列序列的单个特定步骤，而不是索引整个排列结果？ - Paul Sasik

我知道答案已经被接受了，但这是一个非常好的问题，有一组聪明的答案。我会让作者决定，但我建议使用更好的标题，比如：“如何计算第N个排列步骤？”“索引到不存在的集合”并没有真正传达问题，我个人认为。 - Paul Sasik

@Paul Sasik：同意。 已更改。 顺便说一下，我确实使用了 @LBushkin 和 @Martin Liversage 提供的想法变化来解决一个与此问题非常相关的问题。 - Steven Evers

@Paul - 我认为“排列”不正确。至少在最简单的形式中，每个不同的项只允许在该列表中的每个序列中出现一次。你可以从一个袋子/多重集合中争辩出一个排列，但在我看来那是耍赖;-) LBushkin说这个问题可以用笛卡尔积来解决。严谨地说，我认为这也不对——我认为序列的列表就是笛卡尔积。 - user180247

Answer 1

提示：思考一下如何用字母代替数字在基数26而不是基数10打印数字。对于以任意基数显示数字的一般算法是什么？

提示：（向右滚动查看）

                                                                                      int ndx1 = currentIndex / 26 / 26 % 26;
                                                                                      int ndx2 = currentIndex / 26 % 26;
                                                                                      int ndx3 = currentIndex % 26;

- John Kugelman

Answer 2

假设有26个字符，类似于这样的东西应该可以工作：

public string CurrentSequence(int currentIndex) {
    return characters[currentIndex / (26 * 26)] 
        + characters[(currentIndex / 26) % 26]
        + characters[currentIndex % 26];
}

- recursive

Answer 3

哇，一天内有两个问题都可以通过笛卡尔积来解决。太神奇了。

您可以使用Eric Lippert的LINQ代码片段来生成所有索引值的组合。这种方法产生一个流式的值集合，因此它们不需要在内存中存储。这种方法很好地将生成代码的逻辑与维护状态或使用代码执行计算分开。

Eric的所有组合代码：

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)  
{  
  IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };  
  return sequences.Aggregate(  
    emptyProduct,  
    (accumulator, sequence) =>   
      from accseq in accumulator   
      from item in sequence   
      select accseq.Concat(new[] {item}));                 
} 

现在你可以写：

public static IEnumerable<string> AllCodes()
{
  char[] characters = {a, b, c... z}; 
  IEnumerable<char[]> codeSets = new[] { characters, characters, characters };

  foreach( var codeValues in codeSets.CartesianProduct() )
  {
    yield return 
       string.Format( "{0}{1}{2}", codeValues[0], codeValues[1], codeValues[2]);
  }
}

上面的代码生成一个从aaa到zzz的所有代码字符串的流序列。现在，您可以在其他地方使用它来执行处理：

foreach( var code in AllCodes() )
{
    // use the code value somehow...
}

- LBushkin

---

该解决方案无法高效地查找索引，而这正是使用情况。 - recursive

@递归。也许。除非OP表明软件无论如何都会遍历所有索引。因此这仍然可能有所帮助。 - LBushkin

递归是正确的，但确实非常有用。我看过Eric关于这个的帖子，但已经忘记了。+1 - Steven Evers

我不认为查找索引是使用案例。我把它看作是OP试图解决大型内存列表问题的尝试，而我认为在考虑到问题所定义的要求时，使用惰性枚举器是更可取的解决方案。 - Jay

Answer 4

有多种方法可以解决您的问题，但其中一种选项是动态生成序列而不是将其存储在列表中：

IEnumerable<String> Sequence() {
  for (var c1 = 'a'; c1 <= 'z'; ++c1)
    for (var c2 = 'a'; c2 <= 'z'; ++c2)
      for (var c3 = 'a'; c3 <= 'z'; ++c3)
        yield return String.Format("{0}{1}{2}", c1, c2, c3);
}

您可以枚举所有字符串：

foreach (var s in Sequence())
  Console.WriteLine(s);

这段代码完全没有使用索引，它允许你使用简单的代码在字符串序列周围创建一个循环，而不需要存储这些字符串。

- Martin Liversage