2

我正在使用排列生成一个字符串（使用它的每个字符）到“helloworld！”，但是它花了...176791 到“helloworld！” 有没有办法让我可以输入：176791 快速排列为“helloworld！”？

        ...
176790. helloworl!d
176791. helloworld!

我的代码：

#include <windows.h>
#include <string>
#include <iostream>
#include <algorithm>

int main( void )
{
    ::UINT64 Count = 0;
    std::string SomeString = "eohldo!lwrl";
    do
    {
        Count ++;
        std::cout << Count << ". " << SomeString << std::endl;
        if( SomeString == "helloworld!" )
            break;
    } while( std::next_permutation( SomeString.begin( ), SomeString.end( ) ) );

    ::getchar( );
    return( 0 );
};
4

1 回答 1

3

我不确定这个问题是关于什么的。基本上，看起来您正在寻找一种通过整数“编码”排列的方法。但尚不清楚这种编码是否需要与顺序调用生成的排列序列同步std::next_permutation。是吗？即您是否要求该数字176791编码由176791应用程序产生的排列std::next_permutation？

排列可以用几种不同的方式用整数编码。正确构造的编码都将占用相同的位数。但是不同的编码可能会使用不同的整数来编码相同的排列。

无论如何，如果您不关心特定的编码方法，那么N元素的任何排列都可以按以下方式编码：

  • 想象一下排列的规范表示：描述序列元素新位置的索引数组N，即index[old position] = new position.

  • 现在只需将该数组解释为 base 中的 N 位数字N。即排列由一个整数值表示

    index[0]*N^0 +  index[1]*N^1 + index[2]*N^2 + ... + index[N-1]*N^(N-1)

基本上，原始排列的规范数组表示被打包成一个足够大的整数值。（如果N是 2 的幂，则此表示将简单地将原始数组值打包到位数组中）。打包和拆包都是一个简单的过程。

不幸的是，我上面描述的表示结构并不完善。它需要比必要更多的位，因为它试图“无损”编码index具有非唯一值的数组。置换的有效表示在索引数组中不会有重复值。这立即意味着上述表示是过度的。更紧凑的表示应该是可能的。无论如何，这应该是一个经过充分研究的主题，一个简单的谷歌搜索应该会找到很多关于编码排列的信息。

这是一个 SO 链接，提供了对该主题的更深入分析

快速排列 -> 数字 -> 排列映射算法

于 2012-11-29T03:49:12.157 回答