c++ - 随机排列单链表的前 N ​​个元素

Question

我必须随机排列长度为 n 的单链表的 N 个第一个元素。每个元素定义为:

typedef struct E_s
{
  struct E_s *next;
}E_t;

我有一个根元素，我可以遍历整个大小为 n 的链表。随机排列仅 N 个第一个元素(从根开始)的最有效技术是什么？

所以，给定 a->b->c->d->e->f->...x->y->z 我需要做点什么。比如 f->a->e->c->b->...x->y->z

我的具体情况:

• n-N 大约是 n 的 20%
• 我的 RAM 资源有限，最好的算法应该到位
• 我必须在循环中进行多次迭代，所以速度确实很重要
• 不需要理想的随机性(均匀分布)，“几乎”随机就可以
• 在进行排列之前，我已经遍历了 N 个元素(用于其他需要)，所以也许我也可以将其用于排列

更新:我找到了 this paper .它指出它提出了一种 O(log n) 堆栈空间和预期 O(n log n) 时间的算法。

Answer 1

我没试过，但你可以使用“随机 merge-sort”。

更准确地说，您将 merge 例程随机化。您没有系统地合并两个子列表，而是基于抛硬币来进行合并(即以 0.5 的概率选择第一个子列表的第一个元素，以 0.5 的概率选择正确的子列表的第一个元素)。

这应该在 O(n log n) 中运行并使用 O(1) 空间(如果正确实现)。

您可以在下面找到一个 C 中的示例实现，您可以根据自己的需要进行调整。请注意，此实现在两个地方使用随机化:在 splitList 和 merge 中。但是，您可以只选择这两个地方之一。我不确定分布是否是随机的(我几乎可以肯定它不是)，但一些测试用例产生了不错的结果。

#include <stdio.h>
#include <stdlib.h>

#define N 40

typedef struct _node{
  int value;
  struct _node *next;
} node;

void splitList(node *x, node **leftList, node **rightList){
  int lr=0; // left-right-list-indicator
  *leftList = 0;
  *rightList = 0;
  while (x){
    node *xx = x->next;
    lr=rand()%2;
    if (lr==0){
      x->next = *leftList;
      *leftList = x;
    }
    else {
      x->next = *rightList;
      *rightList = x;
    }
    x=xx;
    lr=(lr+1)%2;
  }
}

void merge(node *left, node *right, node **result){
  *result = 0;
  while (left || right){
    if (!left){
      node *xx = right;
      while (right->next){
    right = right->next;
      }
      right->next = *result;
      *result = xx;
      return;
    }
    if (!right){
      node *xx = left;
      while (left->next){
    left = left->next;
      }
      left->next = *result;
      *result = xx;
      return;
    }
    if (rand()%2==0){
      node *xx = right->next;
      right->next = *result;
      *result = right;
      right = xx;
    }
    else {
      node *xx = left->next;
      left->next = *result;
      *result = left;
      left = xx;
    }
  }
}

void mergeRandomize(node **x){
  if ((!*x) || !(*x)->next){
    return;
  }
  node *left;
  node *right;
  splitList(*x, &left, &right);
  mergeRandomize(&left);
  mergeRandomize(&right);
  merge(left, right, &*x);
}

int main(int argc, char *argv[]) {
  srand(time(NULL));
  printf("Original Linked List\n");
  int i;
  node *x = (node*)malloc(sizeof(node));;
  node *root=x;
  x->value=0;
  for(i=1; i<N; ++i){
    node *xx;
    xx = (node*)malloc(sizeof(node));
    xx->value=i;
    xx->next=0;
    x->next = xx;
    x = xx;
  }
  x=root;
  do {
    printf ("%d, ", x->value);
    x=x->next;
  } while (x);

  x = root;
  node *left, *right;
  mergeRandomize(&x);
  if (!x){
    printf ("Error.\n");
    return -1;
  }
  printf ("\nNow randomized:\n");
  do {
    printf ("%d, ", x->value);
    x=x->next;
  } while (x);
  printf ("\n");
  return 0;
}