有没有一种方法可以轻松地计算出具有特定数量集合位的所有数字的序列？
例如，我想将所有2位的数字设置为最多4位：
3: has 2 bits set to true
5: ,,
6: ,,
9: ,,
10: ,,
12: ,,
有没有一种方法可以在不手动计数的情况下确定这些数字？
编辑：数字的顺序实际上并不相关。我确实想知道获得所有这些的最快方法，尽管对于特定数量的比特集和最大数量的比特。(我不需要一种可以确定这个序列中第n个数字的方法(
第2版：我想要的原因是能够获得列表中元素的组合，就像这里所做的：值列表的所有可能组合。这个解决方案将给出所有的组合，其中我只想要具有正好8个唯一值的组合。
是的，有一个比特技巧可以在n的位置生成k集合比特的所有组合。
此处描述。
using System;
public class Test
{
public static void Main()
{
int k = 2;
int n = 4;
int v = (1 << k) - 1;
int finish = v << (n - k);
Console.WriteLine(v);
while (v != finish) {
int t = (v | (v - 1)) + 1;
v = t | ((((t & -t) / (v & -v)) >> 1) - 1);
Console.WriteLine(v);
}
}
}
MBo的答案是一个优雅的解决方案，如果您的总集合少于64个元素。如果你有更多的元素，这里有一个迭代器，它将从一组n个元素中生成所有k个元素的组合，以解决你的根问题。
using System;
using System.Collections;
using System.Collections.Generic;
namespace CPHUtils
{
public class CombinationIterator : IEnumerable<int[]>
{
private int setSize;
private int combinationSize;
private int[] indices;
private int indexToIncrement;
/// <summary>
/// Public constructor takes total set size and number of elements in the combinations to be returned
/// </summary>
/// <param name="combinationSize_"></param>
public CombinationIterator(int combinationSize_, int setSize_)
{
if (combinationSize_ <= 0) throw new ArgumentException(string.Format("{0} ({1}) is <= 0", nameof(combinationSize_), combinationSize_));
if (setSize_ <= 0) throw new ArgumentException(string.Format("{0} ({1}) is <= 0", nameof(setSize_), setSize_));
if (combinationSize_ > setSize_) throw new ArgumentException(string.Format("{0} ({1}) is <= {2} ({3})",
nameof(combinationSize_), combinationSize_, nameof(setSize_), setSize_));
this.combinationSize = combinationSize_;
this.setSize = setSize_;
// Create internal list of indices with one additional element to make comparison easier during iteration
indices = new int[combinationSize + 1];
for (int i = 0; i < combinationSize; i++)
{
indices[i] = i;
}
indices[combinationSize] = setSize;
}
/// <summary>
/// Returns subsequent arrays of <see cref="combinationSize"/> indices to enumerate all unique
/// combinations of elements taken from a set of size <see cref="setSize"/>.<br/>
/// Based on https://en.wikipedia.org/wiki/Combination "simpler faster way"<br/>
/// There are many ways to enumerate k combinations. One way is to visit all the binary numbers less than 2n.
/// Choose those numbers having k nonzero bits, although this is very inefficient even for small n
/// (e.g. n = 20 would require visiting about one million numbers while the maximum number of allowed k combinations
/// is about 186 thousand for k = 10). The positions of these 1 bits in such a number is a specific k-combination of
/// the set { 1, …, n }.[8] Another simple, faster way is to track k index numbers of the elements selected,
/// starting with {0 .. k−1} (zero-based) or {1 .. k} (one-based) as the first allowed k-combination and then
/// repeatedly moving to the next allowed k-combination by incrementing the last index number if it is lower
/// than n-1 (zero-based) or n (one-based) or the last index number x that is less than the index number
/// following it minus one if such an index exists and resetting the index numbers after x to {x+1, x+2, …}.
/// </summary>
/// <returns>Subsequently returns an array of <see cref="combinationSize"/> int's such that each element
/// is the index of an element in the original set, until all such unique combinations have been enumerated.</returns>
public IEnumerator<int[]> GetEnumerator()
{
// On first call the array is already set up, can return it directly
int[] result = new int[combinationSize];
Array.Copy(indices, result, combinationSize);
yield return result;
indexToIncrement = combinationSize - 1;
while (indexToIncrement >= 0)
{
// Increment at this index until done there
while (indices[indexToIncrement] < (indices[indexToIncrement + 1] - 1))
{
indices[indexToIncrement]++;
result = new int[combinationSize];
Array.Copy(indices, result, combinationSize);
yield return result;
}
// Now start at next lower index
indexToIncrement--;
// Are we done?
if (indexToIncrement < 0) yield break;
// Room for further iterations here?
if (indices[indexToIncrement] < (setSize - combinationSize + indexToIncrement))
{
indices[indexToIncrement]++;
for (int i = indexToIncrement + 1; i < combinationSize; i++)
{
indices[i] = indices[i - 1] + 1;
}
result = new int[combinationSize];
Array.Copy(indices, result, combinationSize);
yield return result;
// If there is more room at the top, we need to start there again
if (indices[combinationSize - 1] < (setSize - 1))
{
indexToIncrement = combinationSize - 1;
}
}
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
}
这就是你使用它的方式：
[Theory]
[InlineData(1, 1, "A")]
[InlineData(2, 2, "AB")]
[InlineData(1, 4, "ABCD")]
[InlineData(2, 4, "ABACADBCBDCD")]
[InlineData(3, 4, "ABCABDACDBCD")]
[InlineData(3, 3, "ABC")]
public void genericCombinationIteratorUnitTest(int combinationSize, int setSize, string expectedValue)
{
string[] data = new string[setSize];
for (int i = 0; i < setSize; i++)
{
data[i] = ((char)(((int)'A') + i)).ToString();
}
CombinationIterator enumerator = new CombinationIterator(combinationSize, setSize);
StringBuilder sb = new StringBuilder();
foreach (int[] combination in enumerator)
{
foreach (int ix in combination)
{
sb.Append(data[ix]);
}
}
string result = sb.ToString();
Assert.Equal(expectedValue, result);
}