1

我有一个类似于这里描述的问题：

从 n 返回 k 个元素的所有组合的算法

我正在寻找类似的东西，涵盖 n 中 k 的所有可能组合。但是，我需要一个子集来与之前绘制的有很大不同。例如，如果我要从一组 8 个元素中绘制 3 个元素的子集，则以下算法对我没有用处，因为每个子集都与之前绘制的子集非常相似：

11100000, 11010000, 10110000, 01110000, ...

我正在寻找一种以更“随机”的方式选择子集的算法，即。其中一个子集中的大多数元素不会在下一个子集中重用：

11100000, 00010011, 00101100, ...

有人知道这样的算法吗？

我希望我的问题有意义并且有人可以帮助我=）

亲切的问候，

基督教

4

6 回答 6

1

这不是真正随机的，但根据您的需要，它可能适合您。

  1. 计算可能的组合数。让我们将它们命名为 N。
  2. 计算一个与 N 互质的大数。我们将其命名为 P。
  3. 对组合排序并给它们从 1 到 N 的数字。让我们将它们命名为 C 1到 C N
  4. 迭代输出组合。第一个是 V P mod N，第二个是 C 2*P mod N，第三个是 C 3*P mod N等等。本质上，Output i = C i*P mod N. Mod 的意思作为模运算符。

如果仔细挑选 P，你会得到看似随机的组合。接近 1 或 N 的值将产生差异很小的值。更好地选择接近 N/4 或 N/5 的值。您还可以为您需要的每次迭代随机生成 P。

于 2009-05-11T12:01:40.117 回答
1

作为我对这个答案的评论的后续，这里有一些代码，允许人们按照 colex 顺序从其“索引”确定子集的组成。无耻地从我自己的任务中偷走。

//////////////////////////////////////
// NChooseK
//
// computes    n!
//          --------
//          k!(n-k)!
//
// using Pascal's identity
// i.e. (n,k) = (n-1,k-1) + (n-1,k)
//
// easily optimizable by memoization
long long NChooseK(int n, int k)
{
    if(k >= 0 && k <= n && n >= 1)
    {
        if( k > n / 2)
            k = n - k;
        if(k == 0 || n == 0)
            return 1;
        else
            return NChooseK(n-1, k-1) + NChooseK(n-1, k);
    } 
    else
        return 0;
}

///////////////////////////////////////////////////////////////////////
// SubsetColexUnrank
//  The unranking works by finding each element
//  in turn, beginning with the biggest, leftmost one.
//  We just have to find, for each element, how many subsets there are
//  before the one beginning with the elements we have already found.
//
// It stores its results (indices of the elements present in the subset) into T, in ascending order.
void SubsetColexUnrank(long long r, int * T, int subsetSize)
{
    assert( subsetSize >= 1 );

    // For each element in the k-subset to be found
    for(int i = subsetSize; i >= 1; i--)
    {
        // T[i] cannot be less than i
        int x = i;

        // Find the smallest element such that, of all the k-subsets that contain it,
        // none has a rank that exceeds r.            
        while( NChooseK(x, i) <= r )
            x++;

        // update T with the newly found element
        T[i] = x;

        // if the subset we have to find is not the first one containing this element
        if(r > 0)
        {
            // finding the next element of our k-subset
            // is like finding the first one of the same subset
            // divided by {T[i]}
            r -= NChooseK(x - 1, i);
        }
    }
}

随机输入，随机输出。

colex order 是这样的，它的 unranking 函数不需要从中选择要工作的元素的集合的大小；元素的数量假定为 NchooseK（集合的大小，子集的大小）。

于 2009-05-12T02:36:43.643 回答
1

首先从 n 生成 k 的所有可能组合，然后在随机函数的帮助下重新排列它们怎么样？

如果您在向量中有结果，请循环遍历向量：对于每个元素，让它随元素在随机位置改变位置。

对于较大的 k 和 n，这当然会变得很慢。

于 2009-05-11T10:16:12.173 回答
0

如何随机选择 k 个元素。即选择p在1和n之间随机的第p个，然后重新排序剩下的并选择q在1和n-1之间的第q个等等？

或者我误解了。你还想要所有的可能性吗？在这种情况下，您始终可以先生成它们，然后从列表中选择随机条目

于 2009-05-11T10:13:35.050 回答
0

根据你想要做的事情，你可以做一些像打牌这样的事情。保留两个列表：Source是您的源（未使用）列表；第二个Used是“已选中”列表。当您从 中随机选择k项目时Source，您将它们移动到您的Used列表中。

如果当您需要再次挑选时还有k剩余的物品，则将它们全部挑选并交换列表。Source如果少于k项目，则从中选择j项目Used并将它们添加到中Source以制作k项目Source，然后将它们全部选择并交换列表。

这有点像k从一副牌中挑选牌。你把它们扔到用过的堆里。一旦你到达终点或需要更多牌，你就将旧的牌重新洗牌。

这只是为了确保每个集合都与之前的子集绝对不同。此外，这并不能真正保证在旧子集开始重复之前选择所有可能的子集。

好处是您无需担心预先计算所有子集，并且您的内存需求与您的数据成线性关系（2 个n大小的列表）。

于 2009-05-12T14:08:35.860 回答
0

通过“随机查找”，我认为您的意思是字典上的距离。这是否适用于组合ivs.i-1或ivs. 所有以前的组合？

如果是这样，这里有一些建议：

  • 由于大多数组合器产生有序输出，因此有两种选择：

    1. 设计或找到以某种方式产生无序输出的生成器
    2. 枚举并存储足够的/所有组合在一个 tie'd 数组文件/db

  • 如果您决定选择 2 号门，那么您可以通过 1 和组合数之间的随机整数访问随机排序的组合

  • 作为最后的检查，使用组合之间差异/距离的度量来比较当前和以前的组合，例如对于Bit::VectorPerl 中的无符号：

    $vec1->Lexicompare($vec2) >= $MIN_LEX_DIST

  • 您可能会再看看 #1 门后面，因为即使是中等的值，n您k也可以获得一个大数组：

C(n,k) = n!/(k!(nk)!)

编辑：

刚刚看到您对 AnnK 的评论......也许 lexicompare 可能仍然可以帮助您跳过类似的组合？

于 2009-05-11T11:39:34.643 回答