Project Euler Problem 276, 268, 347

〇〇

〇〇 发表于 2012-1-15 07:14
Problem 367
14 January 2012

在计算机科学中，Bogo排序（bogo-sort）是个既不实用又原始的排序算法，其原理等同将一堆卡片抛起，落在桌上后检查卡片是否已整齐排列好，若非就再抛一次。其名字源自Quantum bogodynamics，又称bozo sort、blort sort或猴子排序（参见无限猴子定理）。

目录 [隐藏] 1 实现 1.1 Python 1.2 Java 2 运行时间 3 相关算法 3.1 Bozo排序 3.2 量子Bogo排序 4 参见 5 参考资料 6 外部链接

[编辑] 实现以下是伪代码：
函數 bogosort(陣列)   當 非 有序(陣列)      陣列 := 隨機排列(陣列)其平均时间复杂度是 O(n × n!)，在最坏情况所需时间是无限。它并非一个稳定的算法。
[编辑] Python

from random import shufflefrom itertools import izip, tee def in_order(my_list):    """Check if my_list is ordered"""    it1, it2 = tee(my_list)    it2.next()    return all(a<=b for a,b in izip(it1, it2)) def bogo_sort(my_list):    """Bogo-sorts my_list in place."""    while not in_order(my_list):        shuffle(my_list)

[编辑] Java

Random random = new Random(); public void bogoSort(int[] n) {    while(!inOrder(n))shuffle(n);} public void shuffle(int[] n) {    for (int i = 0; i < n.length; i++) {        int swapPosition = random.nextInt(i + 1);        int temp = n[i;        n[i = n[swapPosition;        n[swapPosition = temp;    }} public boolean inOrder(int[] n) {    for (int i = 0; i < n.length-1; i++) {        if (n[i > n[i+1]) return false;    }    return true;}

[编辑] 运行时间这个排序算法基于可能性。平均而言，让所有元素都被排好序的期望比较次数渐近于(e − 1)n!，期望的位置交换次数渐近(n − 1)n!。[1]期望的位置交换次数增长地比期望比较次数快，是因为只需要比较几对元素就能发现元素是无序的，但是随机地打乱顺序所需要的交换次数却与数据长度成比例。在最差的情况下，交换和比较次数都是无限的，这就像随机投掷硬币可能连续任意次正面向上。
最好的情况是所给的数据是已经排好序的，这种情况下不需要任何位置交换，而比较次数等于n - 1。
对任何固定长度的数据，算法的预期运行时间像无限猴子定理一样是无限的：总有一些可能性让被正确排好序的序列出现。
[编辑] 相关算法[编辑] Bozo排序Bozo排序是另一个基于随机数的算法。如果列表是无序的，就随机交换两个元素的位置再检查列表是否有序。
[编辑] 量子Bogo排序计算机科学家之间的一个笑话说：量子计算机能够以 O(n) 的复杂度更有效地实现Bogo排序。这将使用真正的量子的随机性来随机打乱列表。根据量子物理学的多世界诠释，量子的随机性分别在无限的宇宙序列中展开，其中的一些将会提供一个排好序的列表。因为需要重新排列的次数虽然很大但仍然是有限的。这个列表接着就被测试出来（需要n-1次比较）。接着，计算机就应该实施“摧毁宇宙”的操作，使得在剩下的宇宙中的观察者能够得到一个排好序的列表。
[编辑] 参见

• 暴力搜寻法
  

[编辑] 参考资料

• ^ H. Gruber, M. Holzer and O. Ruepp: Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms, 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, pp. 183-197.
  

[编辑] 外部链接

• Jargon File上的条目
• Bogosort: an implementation that runs on Unix-like systems, similar to the standard sort program.
• Bogosort: Simple C++ implementation of bogosort algorithm
  

〇〇

224的部分结果：
a2=a1-2b1+2c1,b2=2a1-b1+2c1,c2=b2+1
下一个a1 b1 c1= a2 b2 c2

a1	b1	c1	a2	b2	c2
2	2	3	4	8	9
4	8	9	6	18	19
6	18	19	8	32	33
8	32	33	10	50	51
10	50	51	12	72	73
12	72	73	14	98	99
14	98	99	16	128	129
16	128	129	18	162	163
18	162	163	20	200	201
20	200	201	22	242	243
22	242	243	24	288	289
24	288	289	26	338	339
26	338	339	28	392	393
28	392	393	30	450	451
30	450	451	32	512	513
32	512	513	34	578	579
34	578	579	36	648	649
36	648	649	38	722	723
38	722	723	40	800	801
40	800	801	42	882	883

a2=a1+2b1+2c1 b2=2a1+b1+2c1 c2=2a1+2b1+3c1

a1	b1	c1	a2	b2	c2
2	2	3	12	12	17
12	12	17	22	46	51
22	46	51	32	100	105
32	100	105	42	174	179
42	174	179	52	268	273
52	268	273	62	382	387
62	382	387	72	516	521
72	516	521	82	670	675
82	670	675	92	844	849
92	844	849	102	1038	1043
102	1038	1043	112	1252	1257
112	1252	1257	122	1486	1491
122	1486	1491	132	1740	1745
132	1740	1745	142	2014	2019
142	2014	2019	152	2308	2313
152	2308	2313	162	2622	2627
162	2622	2627	172	2956	2961
172	2956	2961	182	3310	3315
182	3310	3315	192	3684	3689
192	3684	3689	202	4078	4083

〇〇

〇〇 发表于 2012-1-18 14:51
224的部分结果：
a2=a1-2b1+2c1,b2=2a1-b1+2c1,c2=b2+1
下一个a1 b1 c1= a2 b2 c2

第一组实际上是(2n)^2+(2n^2)^2+1==(2n^2+1)^2，不需要递推

只要满足a+b+c<75e6即解不等式2n+2n^2+2n^2+1<=75e6求出n即可

第二组，有些c和第一组重复，但a,b不同,这些数发生在2*勾股数最大值（直角三角形的斜边）+1的情况，取决于
分解因子是4个还是3个不同的值
如2*25+1=51还可以有2组：
（ 3  4）(1 5)
可以变化成(3+20)(15-4) 46^2+22^2+1=51^2
或(3-20)(15+4) 34^2+38^2+1=51^2

〇〇

224的问题其实就是在a^2+b^2中相邻的数，比如
(0 1)
(1 2)
(4 5)
(8 9)
(9 10)
(16 17)
(17 18)

newkid

367说的是BOZO, 还特意声明不是BOGO.
但是不清楚那个平均次数怎么算出来的。

〇〇

newkid 发表于 2012-1-18 22:41
367说的是BOZO, 还特意声明不是BOGO.
但是不清楚那个平均次数怎么算出来的。

可能与概率有关
第一种方法
比如对
123每次交换2个
有可能产生213 321 132，每种的概率是1/3
对于3!全排列
原数 最少交换次数
123 0
213 1
321 1
132 1
231 2
312 2
而第二种方法 每次随机抛3个
123 抛完后每种都是1/6
1234 抛完后，只有1个数字一定不变

newkid

你是说最少次数的平均值？先把AVG(4!)=24.75 演算一下看看是否对得上。

58楼的C程序我改成PLSQL, 最终数字也是算不出来的因为内存不够大。一千万的如下：

DECLARE
  lim1 NUMBER := 10000000;
  TYPE pt1 IS TABLE OF Node1;
  lv_data pt1:= pt1();
  cn0 NUMBER;
  cn1 NUMBER;
  cnt1 NUMBER :=1;
  a1 NUMBER;
  b1 NUMBER;
  c1 NUMBER;
  a2 NUMBER;
  b2 NUMBER;
  c2 NUMBER;
BEGIN
  lv_data.EXTEND();
  lv_data(1):=Node1(NULL,NULL,NULL,NULL,2,2,3);

  cn0 := 1;
  WHILE cn0 IS NOT NULL LOOP
        a1:=lv_data(cn0).a1;
        b1:=lv_data(cn0).b1;
        c1:=lv_data(cn0).c1;
        
        IF lv_data(cn0).l1 IS NULL THEN
           a2:=a1-2*b1+2*c1;
           b2:=2*a1-b1+2*c1;
           c2:=2*a1-2*b1+3*c1;
           IF a2+b2+c2<=lim1 THEN
              lv_data.EXTEND();
              cn1 := lv_data.COUNT;
              lv_data(cn1):=Node1(cn0,NULL,NULL,NULL,a2,b2,c2);
              lv_data(cn0).l1 := cn1;                 
              cn0 := cn1;
              CONTINUE;
           END IF;
        END IF;

        IF lv_data(cn0).m1 IS NULL THEN
           a2:=a1+2*b1+2*c1;
           b2:=2*a1+b1+2*c1;
           c2:=2*a1+2*b1+3*c1;
           IF a2+b2+c2<=lim1 THEN
              lv_data.EXTEND();
              cn1 := lv_data.COUNT;
              lv_data(cn1):=Node1(cn0,NULL,NULL,NULL,a2,b2,c2);
              lv_data(cn0).m1 := cn1;                 
              cn0 := cn1;
              CONTINUE;
           END IF;
        END IF;


        IF lv_data(cn0).r1 IS NULL THEN
           a2:=-a1+2*b1+2*c1  ;
           b2:=-2*a1+b1+2*c1  ;
           c2:=-2*a1+2*b1+3*c1;
           IF a2+b2+c2<=lim1 THEN
              lv_data.EXTEND();
              cn1 := lv_data.COUNT;
              lv_data(cn1):=Node1(cn0,NULL,NULL,NULL,a2,b2,c2);
              lv_data(cn0).r1 := cn1;                 
              cn0 := cn1;
              CONTINUE;
           END IF;
        END IF;

        cn0 := lv_data(cn0).p1;
        while cn0 IS NOT NULL AND lv_data(cn0).r1 IS NOT NULL LOOP
              cn0 := lv_data(cn0).p1;
        END LOOP;
        
  END LOOP;
  
  -- FOR i IN 1..lv_data.COUNT LOOP
  --     DBMS_OUTPUT.PUT_LINE(lv_data(i).a1||' '||lv_data(i).b1||' '||lv_data(i).c1||' p1='||lv_data(i).p1||' l1='||lv_data(i).l1||' m1='||lv_data(i).m1||' r1='||lv_data(i).r1);
  -- END LOOP;
  
  DBMS_OUTPUT.PUT_LINE('total count='||lv_data.COUNT);
END;
/

total count=1103061

PL/SQL procedure successfully completed.

Elapsed: 00:00:05.52

我用数组实现链表，算是一种练习吧。

newkid

注意到58的C代码及时释放内存空间，我于是改用INDEX BY数组并且加上DELETE操作，终于可以出结果了：


CREATE OR REPLACE  TYPE Node1 IS OBJECT (
        p1 NUMBER
       ,l1 NUMBER
       ,m1 NUMBER
       ,r1 NUMBER
       ,a1 NUMBER
       ,b1 NUMBER
       ,c1 NUMBER
       );
/

DECLARE
  lim1 NUMBER := 75000000;
  TYPE pt1 IS TABLE OF Node1 INDEX BY PLS_INTEGER;
  lv_data pt1;
  cn0 NUMBER;
  cn1 NUMBER;
  cnt1 NUMBER :=1;
  a1 NUMBER;
  b1 NUMBER;
  c1 NUMBER;
  a2 NUMBER;
  b2 NUMBER;
  c2 NUMBER;
BEGIN
  lv_data(1):=Node1(NULL,NULL,NULL,NULL,2,2,3);

  cn0 := 1;
  WHILE cn0 IS NOT NULL LOOP
        a1:=lv_data(cn0).a1;
        b1:=lv_data(cn0).b1;
        c1:=lv_data(cn0).c1;
        
        IF lv_data(cn0).l1 IS NULL THEN
           a2:=a1-2*b1+2*c1;
           b2:=2*a1-b1+2*c1;
           c2:=2*a1-2*b1+3*c1;
           IF a2+b2+c2<=lim1 THEN
              cnt1 := cnt1+1;
              lv_data(cnt1):=Node1(cn0,NULL,NULL,NULL,a2,b2,c2);
              lv_data(cn0).l1 := cnt1;                 
              cn0 := cnt1;
              CONTINUE;
           END IF;
        END IF;

        IF lv_data(cn0).m1 IS NULL THEN
           a2:=a1+2*b1+2*c1;
           b2:=2*a1+b1+2*c1;
           c2:=2*a1+2*b1+3*c1;
           IF a2+b2+c2<=lim1 THEN
              cnt1 := cnt1+1;
              lv_data(cnt1):=Node1(cn0,NULL,NULL,NULL,a2,b2,c2);
              lv_data(cn0).m1 := cnt1;                 
              cn0 := cnt1;
              CONTINUE;
           END IF;
        END IF;


        IF lv_data(cn0).r1 IS NULL THEN
           a2:=-a1+2*b1+2*c1  ;
           b2:=-2*a1+b1+2*c1  ;
           c2:=-2*a1+2*b1+3*c1;
           IF a2+b2+c2<=lim1 THEN
              cnt1 := cnt1+1;
              lv_data(cnt1):=Node1(cn0,NULL,NULL,NULL,a2,b2,c2);
              lv_data(cn0).r1 := cnt1;                 
              cn0 := cnt1;
              CONTINUE;
           END IF;
        END IF;
        
        cn1 := cn0;
        cn0 := lv_data(cn0).p1;
        lv_data.DELETE(cn1);
        while cn0 IS NOT NULL AND lv_data(cn0).r1 IS NOT NULL LOOP
              cn1 := cn0;
              cn0 := lv_data(cn0).p1;
              lv_data.DELETE(cn1);
        END LOOP;
        
  END LOOP;
  
  DBMS_OUTPUT.PUT_LINE('total count='||cnt1||'  array size:'||lv_data.COUNT);
END;
/


total count=8274650  array size:0

PL/SQL procedure successfully completed.

Elapsed: 00:00:39.86

〇〇

newkid 发表于 2012-1-20 00:03
你是说最少次数的平均值？先把AVG(4!)=24.75 演算一下看看是否对得上。

58楼的C程序我改成PLSQL, 最终数 ...

奇怪，我得到的是22.2

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <time.h>
   
5. 
   
6. #define ARRAYSIZE 4
   
7. unsigned int inputArray[ARRAYSIZE]={1,3,2};
   
8. int bogo()
   
9. {
   
10.   int sorted = 1;
    
11.   unsigned int index = 0;
    
12.   unsigned int tmp = 0;
    
13.   unsigned int iterationNo = 0;
    
14.   unsigned int inputArraySize = 4;
    
15.   unsigned int i=0;
    
16.   //srand(clock());
    
17.     //Checking if it's sorted   
    
18.     for(i = 0; i < inputArraySize - 1; i++)
    
19.   {
    
20.         if(inputArray[i] > inputArray[i + 1])
    
21.   {
    
22.           sorted = 0;
    
23.         break;
    
24.       }
    
25.     }
    
26.   //Bogosort Algorithm  
    
27.   while(sorted == 0)
    
28.   {      
    
29.   for(i = 0; i < inputArraySize; i++)
    
30.   {      
    
31.   //Choose a random index with which to swap values      
    
32.   index = (rand() % (inputArraySize - 1));
    
33.       //swap values      
    
34.       tmp = inputArray[i];
    
35.       inputArray[i] = inputArray[index];
    
36.       inputArray[index] = tmp;
    
37.     }
    
38.     sorted = 1;
    
39.     iterationNo++;
    
40.     //printf("%d ",iterationNo);
    
41.     //Checking if it's sorted   
    
42.     for(i = 0; i < inputArraySize - 1; i++)
    
43.   {
    
44.         if(inputArray[i] > inputArray[i + 1])
    
45.   {
    
46.           sorted = 0;
    
47.         break;
    
48.       }
    
49.     }
    
50.   }
    
51.   //printf("%d ",iterationNo);
    
52.   return iterationNo;
    
53. }
    
54. int main(int argc, char **argv)
    
55. {
    
56. int sum=0;
    
57. int a[6][3]={{1,2,3},{2,1,3},{1,3,2},{2,3,1},{3,2,1},{3,1,2}};
    
58. int b[24][4]={{1,2,3,4},{2,1,3,4},{1,3,2,4},{2,3,1,4},{3,2,1,4},{3,1,2,4},
    
59.               {4,1,2,3},{4,2,1,3},{4,1,3,2},{4,2,3,1},{4,3,2,1},{4,3,1,2},
    
60.               {1,4,2,3},{2,4,1,3},{1,4,3,2},{2,4,3,1},{3,4,2,1},{3,4,1,2},
    
61.               {1,2,4,3},{2,1,4,3},{1,3,4,2},{2,3,4,1},{3,2,4,1},{3,1,4,2}};
    
62. srand((unsigned) time(NULL));
    
63. for(int k=0;k<10000;k++)
    
64.   for(int i=0;i<24;i++)
    
65.   {
    
66.   for(int j=0;j<4;j++)
    
67.           {
    
68.                   inputArray[j]=b[i][j];
    
69.                  
    
70.           }
    
71.          
    
72.   sum+=bogo();
    
73. }
    
74. printf("avg=%5.2f",sum/24.0/10000);
    
75.   return 1;
    
76. }
    
77. 
    

复制代码

〇〇

〇〇 发表于 2012-1-20 08:39
奇怪，我得到的是22.2

32行用i和index交换貌似不太随机，改成下面这样，24开头的小数就出来了

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <time.h>
   
5. 
   
6. #define ARRAYSIZE 4
   
7. unsigned int inputArray[ARRAYSIZE]={1,3,2};
   
8. int bozo()
   
9. {
   
10.   int sorted = 1;
    
11.   unsigned int index = 0;
    
12.   unsigned int tmp = 0;
    
13.   unsigned int iterationNo = 0;
    
14.   unsigned int inputArraySize = 4;
    
15.   unsigned int i=0;
    
16.   //srand(clock());
    
17.     //Checking if it's sorted   
    
18.     for(i = 0; i < inputArraySize - 1; i++)
    
19.   {
    
20.         if(inputArray[i] > inputArray[i + 1])
    
21.   {
    
22.           sorted = 0;
    
23.         break;
    
24.       }
    
25.     }
    
26.   //Bogosort Algorithm  
    
27.   while(sorted == 0)
    
28.   {      
    
29.   //for(i = 0; i < inputArraySize; i++)
    
30.   {      
    
31.   //Choose a random index with which to swap values      
    
32.   index = (rand() % (inputArraySize ));
    
33.   unsigned int index1 =index;
    
34.   while(index==index1) index1=(rand() % (inputArraySize ));
    
35.       //swap values      
    
36.       tmp = inputArray[index1];
    
37.       inputArray[index1] = inputArray[index];
    
38.       inputArray[index] = tmp;
    
39.     }
    
40.     sorted = 1;
    
41.     iterationNo++;
    
42.     //printf("%d ",iterationNo);
    
43.     //Checking if it's sorted   
    
44.     for(i = 0; i < inputArraySize - 1; i++)
    
45.   {
    
46.         if(inputArray[i] > inputArray[i + 1])
    
47.   {
    
48.           sorted = 0;
    
49.         break;
    
50.       }
    
51.     }
    
52.   }
    
53.   //printf("%d ",iterationNo);
    
54.   return iterationNo;
    
55. }
    
56. int main(int argc, char **argv)
    
57. {
    
58. int sum=0;
    
59. int a[6][3]={{1,2,3},{2,1,3},{1,3,2},{2,3,1},{3,2,1},{3,1,2}};
    
60. int b[24][4]={{1,2,3,4},{2,1,3,4},{1,3,2,4},{2,3,1,4},{3,2,1,4},{3,1,2,4},
    
61.               {4,1,2,3},{4,2,1,3},{4,1,3,2},{4,2,3,1},{4,3,2,1},{4,3,1,2},
    
62.               {1,4,2,3},{2,4,1,3},{1,4,3,2},{2,4,3,1},{3,4,2,1},{3,4,1,2},
    
63.               {1,2,4,3},{2,1,4,3},{1,3,4,2},{2,3,4,1},{3,2,4,1},{3,1,4,2}};
    
64. srand((unsigned) time(NULL));
    
65. for(int k=0;k<10000;k++)
    
66.   for(int i=0;i<24;i++) //7 don't finish
    
67.   {
    
68.   for(int j=0;j<4;j++)
    
69.           {
    
70.                   inputArray[j]=b[i][j];
    
71.                  
    
72.           }
    
73.          
    
74.   sum+=bozo();
    
75. }
    
76. printf("avg=%5.2f",sum/24.0/10000);
    
77.   return 1;
    
78. }
    

复制代码