迭代洗牌[0..N），而不陣列

Question

我知道有幾個例程的該工作方式如下：

X _{n + 1個} =例程（X _Ñ，最大值）

例如，像一個LCG發生器：

X _{N + 1} =（A * X _n + c）mod m

該生成器中沒有足夠的參數化來生成每個序列。

夢功能：

X _{n + 1個} =例程（X _Ñ，最大，置換數）

此例程，由索引參數到集中的所有的排列，將返回序列中的下一個數字。該序列可能是任意大的（因此存儲陣列和使用事實數字是不切實際的。）

失敗的是，有沒有人有類似的功能指針，無論是無狀態的還是具有恆定量的狀態爲任意'max'，例如他們會迭代一個洗牌列表

Answer 1

是否有可能索引一組排列而不預先計算並將所有內容存儲在內存中？我之前嘗試過類似的方法，但沒有找到解決方案 - 我認爲它是不可能（在數學意義上）

聲明：我可能誤解了你的問題......

Answer 2

從我的迴應another question：

它實際上是可能的 空間成正比，這樣做是爲了 元素的選擇的號碼，而不是設定的 大小，你是從， 不管選擇您選擇的全部集合的比例爲 。這樣做 這通過產生一個隨機 置換，然後從中選擇 這樣的：

選擇一個塊密碼，諸如TEA 或XTEA。使用XOR folding至 將塊大小減小爲最小的 ，其功率比您選擇的集合 大。使用隨機的 種子作爲密碼的關鍵。至 生成 排列中的元素n，使用 加密對n進行加密。如果輸出號碼不在 您的設置中，請將其加密。重複，直到 數字在集合內。在 平均你將不得不做每個生成的數字兩次加密少於 。 這有一個額外的好處，如果 你的種子密碼安全， 所以你的整個排列。

我在這方面寫得更詳細了 here。

當然，還有每一個排列可產生不能保證（並根據您的塊大小和密鑰大小，可能甚至是不可能的），但你可以得到的排列是高度隨機的（如果他們間沒有這不會是一個好的密碼），並且你可以擁有儘可能多的密碼。

Answer 3

如果你想要一個佔用較少堆棧空間的函數，那麼你應該考慮使用迭代版本，而不是函數。您也可以像TreeMap一樣使用數據結構，並將其存儲在磁盤上，並根據需要進行閱讀。

X(n+1) = Routine(Xn, max, permutation number) 
for(i = n; i > 0; i--) 
{ 
    int temp = Map.lookup(i) 
    otherfun(temp,max,perm) 
} 

Answer 4

還有n！ n個元素的排列。存儲你正在使用哪一個需要至少log（n！）/ log（2）位。通過斯特林近似，這大約需要log（n）/ log（2）位。

顯式存儲一個索引需要log（n）/ log（2）位。存儲所有的n，就像在一個索引數組中一樣多n次，或者再次n log（n）/ log（2）。信息理論上，沒有比明確存儲排列更好的方法。

換句話說，您要傳遞的集合中的排列的索引採用相同的漸近存儲空間，就像寫出排列一樣。例如，如果您將排列的索引限制爲32位值，則只能處理多達12個元素的排列。 64位索引只能讓你達到20個元素。

由於指數採取相同的空間置換會，要麼改變你的表現，只是直接使用置換或接受解包成大小N的數組解包置換索引到一個數組

Answer 5

代碼，從索引到排列有一定的映射。有很多其他人，但這個很方便。

#include <math.h> 
#include <stdio.h> 
#include <stdlib.h> 

typedef unsigned char index_t; 
typedef unsigned int permutation; 

static void permutation_to_array(index_t *indices, index_t n, permutation p) 
{ 
    index_t used = 0; 
    for (index_t i = 0; i < n; ++i) { 
     index_t left = n - i; 
     index_t digit = p % left; 
     for (index_t j = 0; j <= digit; ++j) { 
      if (used & (1 << j)) { 
       digit++; 
      } 
     } 
     used |= (1 << digit); 
     indices[i] = digit; 
     p /= left; 
    } 
} 

static void dump_array(index_t *indices, index_t n) 
{ 
    fputs("[", stdout); 
    for (index_t i = 0; i < n; ++i) { 
     printf("%d", indices[i]); 
     if (i != n - 1) { 
      fputs(", ", stdout); 
     } 
    } 
    puts("]"); 
} 

static int factorial(int n) 
{ 
    int prod = 1; 
    for (int i = 1; i <= n; ++i) { 
     prod *= i; 
    } 
    return prod; 
} 

int main(int argc, char **argv) 
{ 
    const index_t n = 4; 
    const permutation max = factorial(n); 
    index_t *indices = malloc(n * sizeof (*indices)); 
    for (permutation p = 0; p < max; ++p) { 
     permutation_to_array(indices, n, p); 
     dump_array(indices, n); 
    } 
    free(indices); 
} 

Answer 6

使用迭代接口的代碼。時間複雜度爲O（n^2），空間複雜度的開銷是：複製n（log n bits），迭代變量（log n bits），跟蹤ni（log n bits），複製當前值（記錄n比特），p（n記錄n比特）的副本，下一個值（記錄n比特）的創建以及一組使用值（n比特）的一組比特。您無法避免n個log n位的開銷。在時間上，這也是O（n^2），用於設置位。這可以稍微減少一點，但是需要使用裝飾樹來存儲使用的值。

這可以通過調用相應的庫來改變爲使用任意的精度整數和位集合，而上述邊界實際上會啓動，而不是在N = 8時被移動（可以移植一個int整數與短小一樣，小至16位）。 9！ = 362880> 65536 = 2^16

#include <math.h> 
#include <stdio.h> 

typedef signed char index_t; 
typedef unsigned int permutation; 

static index_t permutation_next(index_t n, permutation p, index_t value) 
{ 
    permutation used = 0; 
    for (index_t i = 0; i < n; ++i) { 
     index_t left = n - i; 
     index_t digit = p % left; 
     p /= left; 
     for (index_t j = 0; j <= digit; ++j) { 
      if (used & (1 << j)) { 
       digit++; 
      } 
     } 
     used |= (1 << digit); 
     if (value == -1) { 
      return digit; 
     } 
     if (value == digit) { 
      value = -1; 
     } 
    } 
    /* value not found */ 
    return -1; 
} 

static void dump_permutation(index_t n, permutation p) 
{ 
    index_t value = -1; 
    fputs("[", stdout); 
    value = permutation_next(n, p, value); 
    while (value != -1) { 
     printf("%d", value); 
     value = permutation_next(n, p, value); 
     if (value != -1) { 
      fputs(", ", stdout); 
     } 
    } 
    puts("]"); 
} 

static int factorial(int n) 
{ 
    int prod = 1; 
    for (int i = 1; i <= n; ++i) { 
     prod *= i; 
    } 
    return prod; 
} 

int main(int argc, char **argv) 
{ 
    const index_t n = 4; 
    const permutation max = factorial(n); 
    for (permutation p = 0; p < max; ++p) { 
     dump_permutation(n, p); 
    } 
}