随机置换单链表的N个第一个元素

我必须随机地置换长度为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中的示例实现，您可以根据自己的需要进行调整。 请注意，此实现在两个位置使用随机化：在splitList和merge 。 但是，您可以选择这两个地方中的一个。 我不确定分布是否是随机的（我几乎可以肯定它不是），但是一些测试用例产生了不错的结果。

 #include  #include  #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; ivalue=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

转换为数组，使用Fisher-Yates shuffle ，然后转换回列表。

Answer 3

我不相信有任何有效的方法可以在没有中间数据结构的情况下随机混合单链表。 我只是将前N个元素读入数组，执行Fisher-Yates shuffle ，然后将前N个元素重构为单链表。

Answer 4

首先，获取列表的长度和最后一个元素。 你说在随机化之前你已经进行了遍历，那将是个好时机。

然后，通过将第一个元素链接到最后一个元素将其转换为循环列表。 通过将大小除以4来获取列表中的四个指针并迭代它以进行第二次传递。 （这些指针也可以通过在前一次遍历中每四次迭代递增一次，两次和三次来从前一次传递中获得。）

对于随机化传递，再次遍历并以50％的概率交换指针0和2以及指针1和3。 （做两个交换操作或两者都做;只有一个交换将列表分成两个。）

这是一些示例代码。 看起来它可能会更随机，但我想再多几次传球可以做到这一点。 无论如何，分析算法比编写算法更困难：vP。 抱歉没有缩进; 我只是在浏览器中将它打入ideone。

http://ideone.com/9I7mx

 #include  #include  #include  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非常大（因此它不适合您的记忆）的情况，您可以执行以下操作（一种Knuth的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 6

如果你知道N和n，我认为你可以做到这一点。 它也是完全随机的。 您只需遍历整个列表一次，并在每次添加节点时通过随机部分进行迭代。 我认为那是O（n + NlogN）或O（n + N ^ 2）。 我不确定。 它基于在给定先前节点发生的情况下更新为随机部分选择节点的条件概率。

1. 给定先前节点发生的事件，确定为随机部分选择某个节点的概率（p =（N-size）/（n-position），其中size是先前选择的节点数，position是先前考虑的节点数）
2. 如果没有为随机部分选择节点，则转到步骤4.如果为随机部分选择了节点，则根据当前的大小随机选择随机部分的位置（place =（0到1之间的随机）* size，size是再次前一节点的数量）。
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 7

与弗拉德的答案类似，这是一个小的改进（统计上）：

算法中的指数是基于1的。

1. 初始化lastR = -1
2. 如果N <= 1，则转到步骤6。
3. 随机化数字r在1和N之间。

4. 如果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

5. 将N减少1并转到步骤2。
6. 将结果列表的尾部链接到剩余输入列表的头部。 您现在拥有原始列表，其中前N个项目处于排列状态。

由于你没有随机访问，这将减少你在列表中需要的遍历时间（我假设减半，所以渐渐地，你将无法获得任何东西）。

Answer 8

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应该被分成相等大小（+ -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 

Answer 9

对于单链表，有一个算法需要O(sqrt(N))空间和O(N)时间。

它不会在所有排列序列上产生均匀分布，但它可以提供不易区分的良好排列。 基本思想类似于按行和列置换矩阵，如下所述。

算法

设元素的大小为N ， m = floor(sqrt(N)) 。 假设“方阵” N = m*m将使该方法更加清晰。

1. 在第一遍中，您应该将每个元素分隔的元素指针存储为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 p_i->next所有元素p_(i+1)->next链接列表中的下一个大小为O(m)的数组
   • 使用标准方法对此数组进行随机播放
   • 使用此混洗数组重新链接元素

3. 置换每列。

   • 初始化数组A以存储指针p_0, ..., p_m 。 它用于遍历列
   • 对于i = 0到m
   • 索引所有元素在链接列表中以大小为m的数组指向A[0], A[1], ..., A[m-1]
   • 随机播放此arrays
   • 使用此混洗数组重新链接元素
   • 将指针前进到下一列A[i] := A[i]->next

请注意， p_0是指向第一个元素的元素， p_m指向最后一个元素。 另外，如果N != m*m ，则可以对某些p_i使用m+1分离。 现在你得到一个“矩阵”，使得p_i指向每一行的开头。

分析和随机性

1. 空间复杂度：该算法需要O(m)空间来存储行的开始。 用于存储数组的O(m)空间和用于在列置换期间存储额外指针的O(m)空间。 因此，时间复杂度为~O（3 * sqrt（N））。 对于N = 1000000 ，它是大约3000个条目和12kB内存 。

2. 时间复杂度：显然是O(N) 。 它要么逐行或逐列遍历“矩阵”

3. 随机性：首先要注意的是，每个元素都可以通过行和列置换到达矩阵中的任何位置。 元素可以转到链表中的任何位置非常重要。 其次，尽管它不会生成所有排列序列，但它确实生成了部分排列序列。 为了找到排列的数量，我们假设N=m*m ，每行排列有m! 并且有m行，所以我们有(m!)^m 。 如果列排列也包括在内，则它完全等于(m!)^(2*m) ，因此几乎不可能得到相同的序列。

强烈建议至少再重复第二步和第三步以获得更随机的序列。 因为它几乎可以抑制所有行和列的相关性到其原始位置。 当您的列表不是“方形”时，这也很重要。 取决于您的需求，您可能希望使用更多重复。 你使用的重复次数越多，它的排列就越多，随机性就越大。 我记得N=9可以产生均匀分布，我猜可以certificate重复趋于无穷大，它与真正的均匀分布相同。

编辑 ：时间和空间的复杂性是紧密的，在任何情况下几乎都是一样的。 我认为这种空间消耗可以满足您的需求。 如果您有任何疑问，可以在小清单中试用，我认为您会发现它很有用。

Answer 10

下面的列表随机化器具有复杂度O（N * log N）和O（1）内存使用情况。

它基于在我的其他post上描述的递归算法被修改为迭代而不是递归，以便消除O（logN）内存使用。

 #include  #include  #include  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 11

如果满足以下两个条件：

• 你有足够的程序存储器（许多嵌入式硬件直接从闪存执行）;
• 你的解决方案不会遭受你的“随机性”经常重复，

然后，您可以选择一组足够大的特定排列，在编程时定义，编写代码以编写实现每个排列的代码，然后在运行时迭代它们。