241806_zh-TW

liliconcom

JSL 幫助：如何創建向量或列表的所有排列

我試圖找出編寫一些 JSL 來枚舉向量或列表的所有排列的最佳方法。  

 

我發現的一種看起來很有前途的算法是堆算法https://en.wikipedia.org/wiki/Heap%27s_algorithm ，但我似乎不知道如何編碼。有人可以幫我嗎？  

 

我意識到向量或列表的大小越大，輸出的大小就會呈階乘增長（k 項的排列數是 k！ ），所以我也對一種生成排列列表中的每個項目並對該排列進行操作，然後在不再需要生成下一個排列時將其丟棄的方法感興趣。  

回复：JSL 幫助：如何創建向量或列表的所有排列

這是我根據 Craige 的腳本創建的函數。

</CODE></PRE><PRE><CODE class="">Names Default To Here( 1 );
Clear Log();

permutate = Function( {list},
 per = New Namespace();
 per:swap = Function( {targetList, firstPosition, secondPosition}, //returns a list with elements in firstPosition and secondPosition swapped
  {temp},
  temp = targetList[firstPosition];
  targetList[firstPosition] = targetList[secondPosition];
  targetList[secondPosition] = temp;
  Return( targetList );
 );
 per:generate = Function( {k},
  {i, temp},
  If( k == 1,
   Insert Into( per:result, Eval List( List( per:A ) ) ), //else
   per:generate( k - 1 );
        // Generate permutations for kth swapped with each k-1 initial
   For( i = 0, i < k - 1, i += 1, 
            // Swap choice dependent on parity of k (even or odd)
    If( Mod( k, 2 ) == 0,
     per:A = per:swap( per:A, k, i + 1 ), //else
     per:A = per:swap( per:A, 1, k )
    );
    per:generate( k - 1 );
   );
  )
 );
 per:result = {};
 per:A = list;
 per:generate( N Items( per:A ) );
 result = per:result;
 Delete Namespaces( per );
 Return( result );
);



A = {"a", "b", "c", "d"};
permutate( A );

 

回复：JSL 幫助：如何創建向量或列表的所有排列

感謝你們兩位的代碼，很有幫助。遞歸總是讓我頭疼，而且看起來 JSL 並不容易允許您以允許將排列序列的輸出分配給列表或矩陣的方式進行遞歸。  

 

使用生成器函數後，我意識到我想做的事情會花費太多的計算時間。  

 

問題是：有一種用於疫苗功效的衡量標準，它可能無法預防，但可以減輕一種稱為“疾病”的疾病的嚴重程度。減輕分數（MF）。描述的是這裡。它基於 Wilcoxson Rank-Sum 檢驗統計量 (W) 來比較兩組。所以我想要做的是列出給定樣本量的兩組的 W 的所有可能值（使用所有可能的等級排列），然後從中獲取 MF 的所有可能值。我真正想展示的是，我們用於 MF 證明功效的標準相當於在兩組分佈相同的原假設下 W 分佈的臨界值。  

 

我解決問題的方法是假設每個組的基本分佈，並進行模擬研究以獲得這些假設下的 MF 分佈。（另外，對於較大的樣本量，W 在 H0 下是漸近正態的：（總體上沒有差異），所以這也是解決部分問題的另一種方法）。不過，使用模擬還可以讓我檢查不同替代假設下的功效，這使我的分析更加完整。

  

回复：JSL 幫助：如何創建向量或列表的所有排列

你的問題的第二半，如何不是存儲整個列表？

 

好問題；我相信 JMP 提供的唯一答案是讓您的代碼從 JIM 的解決方案執行 print() 或我的解決方案執行 write() 的位置調用。 如果 JMP 提供生成器或協同例程@XanGregg ，您可以有一個更靈活的解決方案，您的代碼可以向生成器詢問您需要的點（或多個點）的下一個序列。 如果您需要的話，提前將它們列出到表格中可能是最好的選擇。

 

您可以分享有關該項目的更多詳細信息嗎？ 全部看完14個需要時間！或 15！排列可能是令人望而卻步的。 如果您希望在查看所有排列之前找到足夠好的答案，也許使用隨機排列，也許使用退火算法，可能是更好的選擇。

回复：JSL 幫助：如何創建向量或列表的所有排列

// Heap's algorithm from https://en.wikipedia.org/wiki/Heap%27s_algorithm
// note: the above uses 0-based arrays, JMP uses 1-based. The above also 
// must be using call-by-reference and JMP uses call-by-value. below uses
// a global array A rather than trying to find a way to pass the array by
// reference. For similar reasons, swap(x,y) is expanded in-line.

generate = Function( {k},
 {i, temp},
 If( k == 1,
  Write( "\!n", A );//
 , //else
  // Generate permutations with kth unaltered
  // Initially k == length(A)
  generate( k - 1 );
        // Generate permutations for kth swapped with each k-1 initial
  For( i = 0, i < k - 1, i += 1, 
            // Swap choice dependent on parity of k (even or odd)
   If( Mod( k, 2 ) == 0,
    temp = A[i + 1];
    A[i + 1] = A[k];
    A[k] = temp;
   , //else
    temp = A[1];
    A[1] = A[k];
    A[k] = temp;
   );
   generate( k - 1 );
  );
 )
);

A = [1 2];
generate( N Cols( A ) );

A = {"a", "b", "c"};
generate( N Items( A ) );

A = 1 :: 4;
generate( N Cols( A ) );

[1 2]
[2 1]
{“a”，“b”，“c”}
{“b”，“a”，“c”}
{"計程車"}
{“a”，“c”，“b”}
{“b”，“c”，“a”}
{“c”，“b”，“a”}
[1 2 3 4]
[2 1 3 4]
[3 1 2 4]
[1 3 2 4]
[2 3 1 4]
[3 2 1 4]
[4 2 1 3]
[2 4 1 3]
[1 4 2 3]
[4 1 2 3]
[2 1 4 3]
[1 2 4 3]
[1 3 4 2]
[3 1 4 2]
[4 1 3 2]
[1 4 3 2]
[3 4 1 2]
[4 3 1 2]
[4 3 2 1]
[3 4 2 1]
[2 4 3 1]
[4 2 3 1]
[3 2 4 1]
[2 3 4 1]

 

感謝您讓我重新訪問維基百科版本！ 上次我剛剛發現了一個更容易轉換的不同變體。

回复：JSL 幫助：如何創建向量或列表的所有排列

我將代碼的非遞歸形式轉換為 JMP。看看這是否有幫助

generate = Function( {n, A}, 
    //c is an encoding of the stack state. c[k] encodes the for-loop counter for when generate(k+1, A) is called
 
 c = {};

 For( i = 1, i <= n, i++, c[i] = 1 );
 Print( A );
    
    //i acts similarly to the stack pointer
 i = 1;
 While( i <= n,
  If( c[i] < i,
   If( Mod( i, 2 ) == 0, 
                //swap(A[0], A[i])
    temp = A[1];
    A[1] = A[i];
    A[i] = temp;
   , 
                //swap(A[c[i]], A[i])
    temp = A[c[i]];
    a[c[i]] = a[i];
    a[i] = temp;
   );
   Print( A );
            //Swap has occurred ending the for-loop. Simulate the increment of the for-loop counter
   c[i] = c[i] + 1; 
            //Simulate recursive call reaching the base case by bringing the pointer to the base case analog in the array
   i = 1;
  , 
        //else
   //Calling generate(i+1, A) has ended as the for-loop terminated. Reset the state and simulate popping the stack by incrementing the pointer.
   c[i] = 1;
   i = i + 1;
  )
 );
);