Случайно переставляем N первых элементов односвязного списка

Ответ 1

Я не пробовал, но вы можете использовать "рандомизированный merge-sort".

Чтобы быть более точным, вы производите случай merge -routine. Вы не объединяете эти два подкатегория систематически, но вы делаете это на основе броска монеты (т.е. С вероятностью 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;
}

Ответ 2

Преобразуйте в массив, используйте Fisher-Yates shuffle и конвертируйте обратно в список.

Ответ 3

Я не считаю, что есть эффективный способ случайного перетаскивания односвязных списков без промежуточной структуры данных. Я просто прочитал первые N элементов в массиве, выполнил Fisher-Yates shuffle, а затем восстановил эти первые N элементов в односвязных список.

Ответ 4

Сначала введите длину списка и последний элемент. Вы говорите, что уже делаете обход перед рандомизацией, это будет хорошее время.

Затем превратите его в круговой список, связав первый элемент с последним элементом. Получите четыре указателя в списке, разделив размер на четыре и пропустив через него второй проход. (Эти указатели также можно получить из предыдущего прохода, увеличивая один, два и три раза за четыре итерации в предыдущем обходе.)

Для прохождения рандомизации перейдите снова и указатели поворота 0 и 2 и указатели 1 и 3 с вероятностью 50%. (Делайте либо обе операции свопинга, либо ни один из них: только один своп разделит список на два.)

Вот пример кода. Похоже, это может быть немного более случайным, но я полагаю, что еще несколько проходов могут сделать трюк. Во всяком случае, анализ алгоритма сложнее, чем его написать: vP. Извинения за отсутствие отступов; Я просто пробил его в идеон в браузере.

http://ideone.com/9I7mx

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

struct list_node {
int v;
list_node *n;
list_node( int inv, list_node *inn )
: v( inv ), n( inn) {}
};

int main() {
srand( time(0) );

// initialize the list and 4 pointers at even intervals
list_node *n_first = new list_node( 0, 0 ), *n = n_first;
list_node *p[4];
p[0] = n_first;
for ( int i = 1; i < 20; ++ i ) {
n = new list_node( i, n );
if ( i % (20/4) == 0 ) p[ i / (20/4) ] = n;
}
// intervals must be coprime to list length!
p[2] = p[2]->n;
p[3] = p[3]->n;
// turn it into a circular list
n_first->n = n;

// swap the pointers around to reshape the circular list
// one swap cuts a circular list in two, or joins two circular lists
// so perform one cut and one join, effectively reordering elements.
for ( int i = 0; i < 20; ++ i ) {
list_node *p_old[4];
copy( p, p + 4, p_old );
p[0] = p[0]->n;
p[1] = p[1]->n;
p[2] = p[2]->n;
p[3] = p[3]->n;
if ( rand() % 2 ) {
swap( p_old[0]->n, p_old[2]->n );
swap( p_old[1]->n, p_old[3]->n );
}
}

// you might want to turn it back into a NULL-terminated list

// print results
for ( int i = 0; i < 20; ++ i ) {
cout << n->v << ", ";
n = n->n;
}
cout << '\n';
}

Ответ 5

В случае, когда N действительно большой (поэтому он не соответствует вашей памяти), вы можете сделать следующее (своего рода Knuth 3.4.2P):

• j = N
• k = случайный между 1 и j
• пересечь список входных данных, найти k-й элемент и вывести его; удалите указанный элемент из последовательности (или отметьте его как-то так, чтобы вы не рассматривали его при следующем обходе)
• уменьшить j и вернуться к 2, если j == 0
• вывести остальную часть списка

Остерегайтесь, что это O (N ^ 2), если вы не можете обеспечить произвольный доступ на шаге 3.

В случае, если N относительно мало, так что N элементов вписывается в память, просто загружайте их в массив и перемешайте, например, @Mitch предлагает.

Ответ 6

Если вы знаете как N, так и n, я думаю, вы можете сделать это просто. Это тоже беспорядочно. Вы только перебираете весь список один раз и через рандомизированную часть каждый раз, когда вы добавляете node. Я думаю, что O (n + NlogN) или O (n + N ^ 2). Я не уверен. Он основан на обновлении условной вероятности того, что a node выбран для случайной части, учитывая то, что произошло с предыдущими узлами.

• Определите вероятность того, что определенная node будет выбрана для случайной части, учитывая то, что произошло с предыдущими узлами (p = (N-size)/(n-position), где размер - это число узлов, выбранных ранее, и позиция количество ранее рассмотренных узлов)
• Если node не выбран для случайной части, перейдите к шагу 4. Если для случайной части выбрано node, произвольно выберите место в случайной части на основе размера (place = (random from 0 и 1) * размер, размер снова является числом предыдущих узлов).
• Поместите node туда, где нужно, обновите указатели. Размер приращения. Перейдите к просмотру node, который ранее указывал на то, что вы просто смотрели и перемещались.
• Приращение позиции, посмотрите на следующий node.

Я не знаю C, но я могу дать вам псевдокод. В этом я отношусь к перестановке в качестве первых рандомизированных элементов.

integer size=0;         //size of permutation
integer position=0      //number of nodes you've traversed so far
Node    head=head of linked list        //this holds the node at the head of your linked list.
Node    current_node=head           //Starting at head, you'll move this down the list to check each node, whether you put it in the list.
Node    previous=head               //stores the previous node for changing pointers.  starts at head to avoid asking for the next field on a null node

While ((size not equal to N) or (current_node is not null)){            //iterating through the list until the permutation is full.  We should never pass the end of list, but just in case, I include that condition)

pperm=(N-size)/(n-position)          //probability that a selected node will be in the permutation.
if ([generate a random decimal between 0 and 1] < pperm)    //this decides whether or not the current node will go in the permutation

    if (j is not equal to 0){   //in case we are at start of list, there no need to change the list       

        pfirst=1/(size+1)       //probability that, if you select a node to be in the permutation, that it will be first.  Since the permutation has
                    //zero elements at start, adding an element will make it the initial node of a permutation and percent chance=1.
        integer place_in_permutation = round down([generate a random decimal between 0 and 1]/pfirst)   //place in the permutation.  note that the head =0.
        previous.next=current_node.next

        if(place_in_permutation==0){            //if placing current node first, must change the head

            current_node.next=head          //set the current Node to point to the previous head
            head=current_node           //set the variable head to point to the current node

        }
        else{
            Node temp=head
            for (counter starts at zero. counter is less than place_in_permutation-1.  Each iteration, increment counter){

                counter=counter.next
            }   //at this time, temp should point to the node right before the insertion spot
            current_node.next=temp.next
            temp.next=current_node
        }
        current_node=previous
    }
    size++              //since we add one to the permutation, increase the size of the permutation
}
j++;
previous=current_node
current_node=current_node.next

}

Вероятно, вы могли бы повысить эффективность, если бы придерживались последнего добавленного node, если вам нужно было добавить его справа от него.

Ответ 7

Если выполняются оба следующих условия:

• у вас много программной памяти (многие встроенные аппаратные средства выполняются непосредственно со вспышки);
• Ваше решение не страдает тем, что ваша "случайность" часто повторяется,

Затем вы можете выбрать достаточно большой набор определенных перестановок, определенный во время программирования, написать код для записи кода, который реализует каждый, а затем перебирать их во время выполнения.

Ответ 8

Подобно ответу Влада, вот небольшое улучшение (статистически):

Индексы в алгоритме основаны на 1.

• Инициализировать lastR = -1
• Если N <= 1 перейти к этапу 6.
• Рандомизировать число r между 1 и N.

• если r!= N

  4.1 Переместите список к элементу r и его предшественнику.

  If lastR != -1
  If r == lastR, your pointer for the of the r'th item predecessor is still there.
  If r < lastR, traverse to it from the beginning of the list.
  If r > lastR, traverse to it from the predecessor of the lastR'th item.
  

  4.2 удалите r-й элемент из списка в список результатов как хвост.

  4.3 lastR = r

• Уменьшите N на единицу и перейдите к шагу 2.
• свяжите хвост списка результатов с заголовком оставшегося списка ввода. Теперь у вас есть исходный список с первичными первыми элементами N.

Поскольку у вас нет случайного доступа, это уменьшит время прохождения, которое вам понадобится в списке (я предполагаю, что в два раза, поэтому асимптотически, вы ничего не выиграете).

Ответ 9

O (NlogN) легко реализовать решение, которое не требует дополнительного хранения:

Предположим, вы хотите рандомизировать L:

• есть L имеет 1 или 0 элементов, которые вы выполнили

• создайте два пустых списка L1 и L2

• цикл над L, деструктивно перемещая его элементы в L1 или L2, выбирая между ними произвольно.

• повторите процесс для L1 и L2 (recurse!)

• присоединить L1 и L2 к L3

• return L3

Обновление

На шаге 3 L следует разделить на равные (+ -1) списки L1 и L2, чтобы гарантировать наилучшую степень сложности (N * log N). Это можно сделать, регулируя вероятность перехода одного элемента в L1 или L2:

p(insert element into L1) = (1/2 * len0(L) - len(L1)) / len(L)

где

len(M) is the current number of elements in list M
len0(L) is the number of elements there was in L at the beginning of step 3

Ответ 10

Существует алгоритм, содержащий O(sqrt(N)) и O(N) время для отдельного списка.

Он не генерирует равномерное распределение по всей последовательности перестановок, но может дать хорошую перестановку, которая не легко различима. Основная идея аналогична перестановке матрицы по строкам и столбцам, как описано ниже.

Алгоритм

Пусть размер элементов N и m = floor(sqrt(N)). Предполагая, что "квадратная матрица" N = m*m сделает этот метод понятным.

• В первом проходе вам следует сохранить указатели элементов, которые разделяются каждым элементом m как p_0, p_1, p_2, ..., p_m. То есть p_0->next->...->next(m times) == p_1 должно быть правдой.

• Перенять каждую строку

  • Для я = от 0 до m:
  • Отметьте все элементы между p_i->next до p_(i+1)->next в списке ссылок массивом размера O(m)
  • Смешать этот массив с помощью стандартного метода
  • Перезапустите элементы, используя этот перетасованный массив.

• Перенять каждый столбец.

  • Инициализировать массив A для хранения указателей p_0, ..., p_m. Он используется для перемещения столбцов
  • Для я = 0 to m do
  • Индекс всех элементов, отмеченных A[0], A[1], ..., A[m-1] в списке ссылок массивом размера m
  • Перемешать этот массив
  • Перезапустите элементы, используя этот перетасованный массив.
  • Переместите указатель на следующий столбец A[i] := A[i]->next

Обратите внимание, что p_0 - это элемент, указывающий на первый элемент, а p_m - на последний элемент. Кроме того, если N != m*m, вы можете использовать m+1 разделение для некоторого p_i. Теперь вы получаете "матрицу", так что p_i указывает на начало каждой строки.

Анализ и случайность

• Сложность пространства: для этого алгоритма требуется O(m) пространство для хранения начала строки. O(m) пространство для хранения массива и O(m) пространство для хранения дополнительного указателя во время перестановки столбцов. Следовательно, временная сложность ~ O (3 * sqrt (N)). Для N = 1000000 оно составляет около 3000 записей и 12 КБ памяти.

• Сложность времени: это, очевидно, O(N). Он либо проходит через "матрицу" по строке или столбцу по столбцу

• Случайность: Первое, что нужно отметить, - это то, что каждый элемент может перемещаться в любом месте матрицы по перестановке строк и столбцов. Очень важно, чтобы элементы могли перемещаться в любой из связанных списков. Во-вторых, хотя он не генерирует всю последовательность перестановок, он генерирует часть из них. Чтобы найти число перестановок, предположим, что N=m*m, каждая перестановка строк имеет m! и существует строка m, поэтому мы имеем (m!)^m. Если также включена перестановка столбцов, она точно равна (m!)^(2*m), поэтому почти невозможно получить одну и ту же последовательность.

Настоятельно рекомендуется повторить второй и третий шаги, по крайней мере, еще раз, чтобы получить более случайную последовательность. Потому что он может подавлять почти всю корреляцию строк и столбцов с ее исходным местоположением. Это также важно, когда ваш список не является "квадратным". В зависимости от ваших потребностей вы можете использовать еще большее количество повторений. Чем больше повторений вы используете, тем больше перестановок может быть и тем более случайным. Я помню, что можно создать равномерное распределение для N=9, и я предполагаю, что можно доказать, что, поскольку повторение стремится к бесконечности, оно совпадает с истинным равномерным распределением.

Изменить: сложность времени и пространства ограничена и практически не меняется в любой ситуации. Я думаю, что это потребление пространства может удовлетворить ваши потребности. Если у вас есть сомнения, вы можете попробовать его в небольшом списке, и я думаю, вы найдете его полезным.

Ответ 11

В списке рандомизатора ниже используется сложность использования O (N * log N) и O (1).

Он основан на рекурсивном алгоритме, описанном на моем другом посту, измененном как итеративный, вместо рекурсивного, чтобы исключить использование памяти O (logN).

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

typedef struct node {
    struct node *next;
    char *str;
} node;


unsigned int
next_power_of_two(unsigned int v) {
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    return v + 1;
}

void
dump_list(node *l) {
    printf("list:");
    for (; l; l = l->next) printf(" %s", l->str);
    printf("\n");
}

node *
array_to_list(unsigned int len, char *str[]) {
    unsigned int i;
    node *list;
    node **last = &list;
    for (i = 0; i < len; i++) {
        node *n = malloc(sizeof(node));
        n->str = str[i];
        *last = n;
        last = &n->next;
    }
    *last = NULL;
    return list;
}

node **
reorder_list(node **last, unsigned int po2, unsigned int len) {
    node *l = *last;
    node **last_a = last;
    node *b = NULL;
    node **last_b = &b;
    unsigned int len_a = 0;
    unsigned int i;
    for (i = len; i; i--) {
        double pa = (1.0 + RAND_MAX) * (po2 - len_a) / i;
        unsigned int r = rand();
        if (r < pa) {
            *last_a = l;
            last_a = &l->next;
            len_a++;
        }
        else {
            *last_b = l;
            last_b = &l->next;
        }
        l = l->next;
    }
    *last_b = l;
    *last_a = b;
    return last_b;
}

unsigned int
min(unsigned int a, unsigned int b) {
    return (a > b ? b : a);
}

randomize_list(node **l, unsigned int len) {
    unsigned int po2 = next_power_of_two(len);
    for (; po2 > 1; po2 >>= 1) {
        unsigned int j;
        node **last = l;
        for (j = 0; j < len; j += po2)
            last = reorder_list(last, po2 >> 1, min(po2, len - j));
    }
}

int
main(int len, char *str[]) {
    if (len > 1) {
        node *l;
        len--; str++; /* skip program name */
        l = array_to_list(len, str);
        randomize_list(&l, len);
        dump_list(l);
    }
    return 0;
}

/* try as:   a.out list of words foo bar doz li 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
*/

Обратите внимание, что эта версия алгоритма полностью не кэширована, рекурсивная версия, вероятно, будет работать намного лучше!