随机置换单链表的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我需要制作smth.像f-> a-> e-> c-> b - > ... x-> y-> z

我的具体案例:

• nN相对于n约为20%
• 我有限的RAM资源,最好的算法应该使它到位
• 我必须在循环中进行多次迭代,因此速度很重要
• 理想的随机性(均匀分布)不是必需的,如果它"几乎"是随机的,那就没关系
• 在进行排列之前,我已经遍历了N个元素(用于其他需求),所以也许我也可以将它用于排列

更新:我发现了这篇论文.它声明它提出了一个O(log n)堆栈空间和预期的O(n log n)时间的算法.

Answer 1

我没试过,但你可以使用"随机合并排序 ".

更准确地说,你随机化了merge-routine.您没有系统地合并这两个子列表,但是您可以基于硬币投掷(即概率为0.5,您选择第一个子列表的第一个元素,概率为0.5,您选择右子列表的第一个元素).

这应该运行O(n log n)并使用O(1)空间(如果正确实施).

下面是C中的示例实现,您可以根据自己的需要进行调整.请注意,此实现在两个位置使用随机化:In splitList和in 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;
}