我需要对长度为n的单向链表的前N个元素进行随机排列。每个元素的定义如下：
typedef struct E_s
{
struct E_s *next;
}E_t;
更新：我找到了这篇论文。它陈述了一种O(log n)堆栈空间和期望的O(n log n)时间复杂度的算法。
我没有尝试过，但你可以使用“随机归并排序”。
更准确地说，你需要随机化merge程序。你不是按照系统性的方式合并两个子列表，而是基于抛硬币（即50%的概率选择第一个子列表的第一个元素，50%的概率选择右侧子列表的第一个元素）进行合并。
这应该以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;
}
O(log n) 的堆栈空间。此外，这个特定的实现既不能保证使用有限的时间，也不能保证使用有限的空间。 - Chris HopmanO(log n) 的堆栈空间中进行修正。此外，不保证使用有限的时间和空间（尽管很有可能），但您可以通过从 splitList 程序中移除随机化来确保这一点，对吧？ - phimuemue将其转换为数组，使用Fisher-Yates shuffle算法进行随机排序，然后再转换回列表。
我认为在没有中间数据结构的情况下，没有有效的方法来随机打乱单向链表。 我会将前N个元素读入数组中，执行Fisher-Yates shuffle，然后将这些前N个元素重构成单向链表。
#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';
}
如果您知道N和n，我认为您可以简单地完成它。 它也是完全随机的。 您只需要遍历整个列表一次，并在每次添加节点时遍历随机部分。 我认为这是O（n + N log N）或O（n + N ^ 2）。 我不确定。 它基于更新给定前一个节点发生了什么的条件概率，即选择用于随机部分的节点。
我不懂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
}
如果您需要在其右侧添加一个节点，那么保留最近添加的节点可能会提高效率。如果N非常大（无法适应您的内存），则可以执行以下操作（一种Knuth的3.4.2P）：
请注意，这是O（N ^ 2），除非您可以确保在步骤3中进行随机访问。
如果N相对较小，因此N个项目适合内存，请像@Mitch建议的那样将它们加载到数组中并进行洗牌。
O(NlogN)易于实现的解决方案，不需要额外的存储空间：
假设您想要随机化L：
如果L有1个或0个元素，则完成
创建两个空列表L1和L2
循环遍历L，将其元素破坏性地移动到L1或L2中，在两者之间随机选择。
对L1和L2重复此过程（递归！）
将L1和L2合并为L3
返回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
#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
*/
与Vlad的答案类似，这里有一个轻微的改进（统计学上）：
算法中的索引是基于1的。
如果 r != N
4.1 遍历列表到第 r 项及其前驱。
如果 lastR != -1
如果 r == lastR，则 r 的前驱指针仍在那里。
如果 r < lastR，则从列表开头遍历到它。
如果 r > lastR，则从最后一项的前驱中遍历到它。
4.2 将第 r 项从列表中移除并作为尾部放入结果列表中。
4.3 lastR = r
由于您没有随机访问，这将减少您在列表中需要遍历的时间（我假设减半，因此渐近地，您不会获得任何好处）。
有一个算法，对于单链表，它需要 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 次) == p_1 应该为真。O(m) 的数组索引链接列表中 p_i->next 到 p_(i+1)->next 之间的所有元素
- 使用标准方法随机洗牌此数组
- 使用此已混洗的数组重新链接元素A 来存储指针 p_0、…、p_m。它用于遍历列。
- 对于 i = 0 到 m：
- 通过大小为 m 的数组索引链接列表中由 A[0]、A[1]、…、A[m-1] 指向的所有元素
- 随机洗牌此数组
- 使用此已混洗的数组重新链接元素
- 将指针前进到下一列 A[i] := A[i]->next
请注意，p_0 是指向第一个元素的元素点，而 p_m 指向最后一个元素。此外，如果 N != m*m，则您可以对某些 p_i 使用 m+1 分隔符。现在，您获得了一个“矩阵”，使得 p_i 指向每行的开头。
空间复杂度：该算法需要 O(m) 的空间来存储行的起始位置，O(m) 的空间来存储数组，以及在列置换期间需要 O(m) 的额外指针空间。因此，时间复杂度约为 O(3*sqrt(N))。对于 N = 1000000，大约有 3000 个条目和12 kB 内存。
时间复杂度：显然是 O(N)。它可以按行或按列遍历“矩阵”。
随机性：首先要注意的是，每个元素都可以通过行和列置换到达矩阵中的任何位置。元素可以到达链表中的任何位置非常重要。其次，虽然它不会生成所有排列序列，但确实会生成其中的一部分。为了找到排列的数量，我们假设 N=m*m，每个行置换有 m! 种可能，而且有 m 行，所以我们有 (m!)^m 种可能。如果包括列置换，则完全等于 (m!)^(2*m)，因此几乎不可能得到相同的序列。
强烈建议至少再重复第二步和第三步一次，以获得更随机的序列。因为它可以抑制几乎所有行和列与其原始位置的相关性。当您的列表不是“正方形”时，这也很重要。根据您的需要，您可能希望使用更多的重复。使用的重复次数越多，排列的可能性就越大，随机性就越高。我记得可以生成N=9的均匀分布，我想可以证明，当重复趋近于无穷大时，它与真正的均匀分布相同。
编辑：时间和空间复杂度是紧密绑定的，在任何情况下几乎都是相同的。我认为这种空间消耗可以满足您的需求。如果您有任何疑问，可以在一个小列表中尝试一下，我认为您会发现它很有用。