随机重排N个第一的单链表元素

本文介绍了随机重排N个第一的单链表元素的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我有重排N个长度为n的单链表第一个元素，随意。每个元素被定义为：

I have to permute N first elements of a singly linked list of length n, randomly. Each element is defined as:

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

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

I have a root element and I can traverse the whole linked list of size n. What is the most efficient technique to permute only N first elements (starting from root) randomly?

因此，考虑到A-> B-> C-> D-> E-> F - > ... X-> Y-> Z I需要做出不便。像F-> A-> E-> C-> B - > ... X-> Y->以Z

So, given a->b->c->d->e->f->...x->y->z I need to make smth. like f->a->e->c->b->...x->y->z

我的具体情况：

N-N相到n约20％是
在我有限的RAM资源，最好的算法应该到位
我必须这样做，在一个循环，在多次迭代，所以速度确实很重要
理想的随机性（均匀分布）不是必需的，这是确定的，如果它是几乎随机
在做出排列，我遍历N个元素已经（对其他需求），所以也许我可以使用它进行置换，以及

更新：我发现<一href="http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V0F-45FKW7V-6B&_user=10&_coverDate=10%2F05%2F1992&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_searchStrId=1576191476&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=53029a9616acb1e9e90017e288d882ef&searchtype=a">this纸。它指出它presents邻算法（log n）的堆栈空间和预期为O（n log n）的时间。

UPDATE: I found this paper. It states it presents an algorithm of O(log n) stack space and expected O(n log n) time.

推荐答案

我还没有尝试过，但你可以使用一个随机的。

I've not tried it, but you could use a "randomized merge-sort".

要更precise，你随机的合并 -routine。你不合并两个子列表系统，但你做的基础上掷硬币（即用概率0.5选择第一个子表的第一个元素，概率0.5您选择合适的子表的第一个元素）。

To be more precise, you randomize the merge-routine. You do not merge the two sub-lists systematically, but you do it based on a coin toss (i.e. with probability 0.5 you select the first element of the first sublist, with probability 0.5 you select the first element of the right sublist).

这应该在运行为O（n log n）的和使用 O（1）空间（如果实施得当）。

This should run in O(n log n) and use O(1) space (if properly implemented).

下面你可以看到在C中的示例实现，你可能会适应你的需求。注意，此实现使用随机在两个地方：在 splitList 和合并。但是，您可能只选择这两个地方之一。我不知道如果分布是随机的（我几乎可以肯定它不是），但一些测试用例取得像样的成绩。

Below you find a sample implementation in C you might adapt to your needs. Note that this implementation uses randomisation at two places: In splitList and in merge. However, you might choose just one of these two places. I'm not sure if the distribution is random (I'm almost sure it is not), but some test cases yielded decent results.

#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;
}

这篇关于随机重排N个第一的单链表元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

SubList