Randomly permute N first elements of a singly linked list

Question

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;

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?

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

My specific case:

• n-N is about 20% relative to n
• I have limited RAM resources, the best algorithm should make it in place
• I have to do it in a loop, in many iterations, so the speed does matter
• The ideal randomness (uniform distribution) is not required, it's Ok if it's "almost" random
• Before making permutations, I traverse the N elements already (for other needs), so maybe I could use this for permutations as well

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

Answer 1

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

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).

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

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

Answer 2

Convert to an array, use a Fisher-Yates shuffle, and convert back to a list.