背景
根据您给出的公式 - w！/ ((wn)! * n!) 看起来您的问题集与处理计算唯一组合数量的二项式系数有关，而不是与处理不同位置重复的排列有关。
你说：
“显然有第三种迭代计算和计数合法排列的方法，直到达到随机索引，但这只是第一种方法的空间换时间权衡，除非有一个计算那些 n 排列的有效方法。
...
这意味着随机数源已经被迫产生比特来区分n！不同的结果都是等价的。我想知道是否有一种有效的方法可以避免依赖这种多余的随机性。也许是通过使用一种算法来产生一个无序的位位置列表，或者通过直接计算第 n 个唯一的位排列。”
因此，有一种方法可以从 k 索引中有效地计算第 n 个唯一组合或排名。k-indexes 指的是唯一的组合。例如，假设采用 4 选择 3 的 n 选择 k 情况。这意味着总共有4个数字可以选择（0、1、2、3），用n表示，它们以3为一组，用k表示。唯一组合的总数可以计算为 n! / ((k! * (nk)!)。0的rank对应(2,1,0)的k-index。rank 1由(3,1,0)的k-index组表示，等等。
解决方案
有一个公式可以用来非常有效地在 k-index 组和相应的排名之间进行转换，而无需迭代。同样，有一个公式可以在等级和相应的 k-index 组之间进行转换。
我写了一篇关于这个公式的论文，以及如何从帕斯卡三角中看出它。这篇论文被称为制表二项式系数。
我编写了一个 C# 类，它位于公共领域，实现了论文中描述的公式。它使用的内存很少，可以从网站下载。它执行以下任务：
将任何 N 选择 K 的所有 k 索引以良好的格式输出到文件。K-indexes 可以替换为更具描述性的字符串或字母。
将 k-index 转换为正确的词典索引或排序二项式系数表中条目的等级。这种技术比依赖迭代的旧已发布技术快得多。它通过使用帕斯卡三角形中固有的数学属性来做到这一点，并且与迭代整个集合相比非常有效。
将已排序二项式系数表中的索引转换为相应的 k 索引。所使用的技术也比旧的迭代解决方案快得多。
使用Mark Dominus方法计算二项式系数，它不太可能溢出并且适用于更大的数字。此版本返回一个长值。至少还有另一种返回 int 的方法。确保使用返回 long 值的方法。
该类是用 .NET C# 编写的，并提供了一种通过使用通用列表来管理与问题相关的对象（如果有）的方法。此类的构造函数采用一个名为 InitTable 的 bool 值，当它为 true 时，将创建一个通用列表来保存要管理的对象。如果此值为 false，则不会创建表。无需创建表即可使用上述 4 种方法。提供了访问器方法来访问表。
有一个关联的测试类，它显示了如何使用该类及其方法。它已经过至少 2 个案例的广泛测试，并且没有已知的错误。
以下经过测试的示例代码演示了如何使用该类并将遍历每个唯一组合：
public void Test10Choose5()
{
String S;
int Loop;
int N = 10; // Total number of elements in the set.
int K = 5; // Total number of elements in each group.
// Create the bin coeff object required to get all
// the combos for this N choose K combination.
BinCoeff<int> BC = new BinCoeff<int>(N, K, false);
int NumCombos = BinCoeff<int>.GetBinCoeff(N, K);
// The Kindexes array specifies the indexes for a lexigraphic element.
int[] KIndexes = new int[K];
StringBuilder SB = new StringBuilder();
// Loop thru all the combinations for this N choose K case.
for (int Combo = 0; Combo < NumCombos; Combo++)
{
// Get the k-indexes for this combination.
BC.GetKIndexes(Combo, KIndexes);
// Verify that the Kindexes returned can be used to retrive the
// rank or lexigraphic order of the KIndexes in the table.
int Val = BC.GetIndex(true, KIndexes);
if (Val != Combo)
{
S = "Val of " + Val.ToString() + " != Combo Value of " + Combo.ToString();
Console.WriteLine(S);
}
SB.Remove(0, SB.Length);
for (Loop = 0; Loop < K; Loop++)
{
SB.Append(KIndexes[Loop].ToString());
if (Loop < K - 1)
SB.Append(" ");
}
S = "KIndexes = " + SB.ToString();
Console.WriteLine(S);
}
}
因此，将类应用于您的问题的方法是将字长中的每一位视为项目总数。这将是 n!/((k! (n - k)!) 公式中的 n。要获得 k 或组大小，只需计算设置为 1 的位数。您必须创建一个列表或数组每个可能的 k 的类对象的个数，在本例中为 32。请注意，该类不处理 N 选择 N、N 选择 0 或 N 选择 1，因此代码必须检查这些情况并返回 1 32 选择 0 情况和 32 选择 32 情况。对于 32 选择 1，它需要返回 32。
如果您需要使用不大于 32 的值，请选择 16（32 个项目的最坏情况 - 产生 601,080,390 个唯一组合），那么您可以使用 32 位整数，这就是当前类的实现方式。如果您需要使用 64 位整数，则必须将类转换为使用 64 位长整数。多头可以持有的最大值是 18,446,744,073,709,551,616，即 2 ^ 64。当 n 为 64 时，n 选择 k 的最坏情况是 64 选择 32。64 选择 32 是 1,832,624,140,942,590,534 - 所以长值适用于所有 64 选择 k 情况. 如果您需要比这更大的数字，那么您可能需要考虑使用某种大整数类。在 C# 中，.NET 框架有一个BigInteger 类。如果您使用不同的语言工作，移植应该不难。
如果您正在寻找一个非常好的 PRNG，那么最快、轻量级和高质量的输出之一就是 Tiny Mersenne Twister 或简称 TinyMT。我将代码移植到 C++ 和 C#。可以在这里找到它，以及原始作者的 C 代码的链接。
与其使用像 Fisher-Yates 这样的洗牌算法，不如考虑做类似以下示例的操作：
// Get 7 random cards.
ulong Card;
ulong SevenCardHand = 0;
for (int CardLoop = 0; CardLoop < 7; CardLoop++)
{
do
{
// The card has a value of between 0 and 51. So, get a random value and
// left shift it into the proper bit position.
Card = (1UL << RandObj.Next(CardsInDeck));
} while ((SevenCardHand & Card) != 0);
SevenCardHand |= Card;
}
上面的代码比任何洗牌算法都快（至少对于获得随机卡片的子集），因为它只适用于 7 张卡片而不是 52 张卡片。它还将卡片打包成单个 64 位字中的各个位。它也使评估扑克牌的效率更高。
另外，请注意，我发现的最好的二项式系数计算器可以处理非常大的数字（它准确地计算了一个结果中产生超过 15,000 位数字的案例）可以在这里找到。