Произвольно переставить 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 составляет около 20% относительно n
• У меня ограниченные ресурсы оперативной памяти, лучший алгоритм должен сделать это на месте
• Я должен сделать это в цикле, во многих итерациях, поэтому скорость имеет значение
• Идеальная случайность (равномерное распределение) не требуется, это нормально, если она "почти" случайна
• Прежде чем делать перестановки, я уже пересекаю N элементов (для других нужд), поэтому, возможно, я мог бы использовать это и для перестановок

ОБНОВЛЕНИЕ: я нашел этот документ . Это заявляет, что представляет алгоритм O (log n) стекового пространства и ожидаемого O (n log n) времени.

Answer 1

Я не пробовал, но вы можете использовать "рандомизированную сортировку слиянием ".

Чтобы быть более точным, вы рандомизируете процедуру 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;
}

Answer 2

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

Answer 3

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

Answer 4

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

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

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

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

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

Answer 5

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

1. Определите вероятность того, что определенный узел будет выбран для случайной части с учетом того, что случилось спредыдущие узлы (p = (N-размер) / (n-позиция), где размер - это количество ранее выбранных узлов, а позиция - количество ранее рассмотренных узлов)
2. Если узел не выбран для случайной части, перейдите кШаг 4. Если узел выбран для случайной части, случайным образом выберите место в случайной части на основе размера (пока = размер = (случайное число от 0 до 1) * размер, размер снова число предыдущих узлов).
3. Поместите узел туда, куда он должен идти, обновите указатели.Размер приращения.Перейдите к просмотру узла, который ранее указывал на то, на что вы только что смотрели и двигались.
4. Увеличение позиции, посмотрите на следующий узел.

Я не знаю 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's 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

}

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

Answer 6

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

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

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

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

Answer 7

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

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

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

Answer 8

В приведенном ниже списке рандомизатора используется сложность 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
*/

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

Answer 9

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

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

Алгоритм

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

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

2. Перестановка каждой строки

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

3. Перестановка каждого столбца.

   • Инициализация массива A для хранения указателей p_0, ..., p_m.Используется для обхода столбцов
   • Для i = 0 до m сделать
   • Индексировать все элементы, отмеченные 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 указывают на начало каждой строки.

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

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

2. Сложность времени: очевидно, O(N).Он либо проходит по «матрице» строка за строкой, либо столбец за столбцом

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

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

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

Answer 10

O (NlogN) простое в реализации решение, не требующее дополнительной памяти:

Скажем, вы хотите рандомизировать L:

1. это L имеет 1 или 0 элементов, которые вы сделали

2. создать два пустых списка L1 и L2

3. перебирает L, разрушительно перемещая свои элементы в L1 или L2, выбирая между двумя случайными числами.

4. повторить процесс для L1 и L2 (рекурсивный!)

5. соединить L1 и L2 в L3

6. возврат L3

Обновление

На шаге 3 L следует разделить на списки L1 и L2 одинакового размера (+ -1), чтобы гарантировать сложность наилучшего случая (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