代码之家 › 专栏 › 技术社区 › Steven Evers

计算第n个置换步?

indexing list math c#

Steven Evers · 技术社区 · 14 年前

我有一个字母a-z的char[26]和via嵌套语句,我正在生成一个序列列表,如:

aaa, aaz... aba, abb, abz, ... zzy, 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)来做一个小例子,并试图用模除法来索引它,但是我今天思考起来有困难,我被难住了。

4 回复 | 直到 14 年前

John Kugelman Michael Hodel 14 年前

:(向右滚动查看)

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

recursive 14 年前

假设有26个字符,这样做应该是可行的:

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

Community CDub 8 年前

two questions in one day 这可以通过笛卡尔积来解决。太神了。

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

所有组合的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...
}

Martin Liversage 14 年前

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

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