计算第N个排列步骤？

Question

我有一个字母az的字符[26]和通过嵌套的语句我正在生成一个序列列表,如:

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)编写一个小例子并尝试使用模数除法进行索引,但是我今天很难思考而且我很难过.

我不是要求答案,只是提供任何帮助.也许正朝着正确的方向发展？

Answer 1

提示:想想如何在基数26而不是基数10中打印数字,并使用字母而不是数字.在任意基数中显示数字的一般算法是什么？

剧透 :(向右滚动查看)

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

Answer 2

这样的事情应该有效,假设有26个字符:

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

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...
}