1. 首頁
  2. 問答
  3. 查找並行化C/C++的第n個排列

查找並行化C/C++的第n個排列

2015-11-29 34 views
1

我目前正在尋找一種方法來查找通過使用函數按照字典順序排列的第n個數組。我有一個從C++庫中使用next_permutation編寫的順序代碼（其餘代碼是普通的舊C），但由於next_permutation的工作方式，它不僅效率低下，而且在並行版本的代碼。我正在使用Open MPI，因此每個進程都必須使用next_permutation，此時數學變得非常混亂。而且，next_permutation每次計算最多爲n，因此每個進程都必須執行比應有的更多的計算。我聽說使用factoradic爲了找到第n個排列，但我一直無法找到任何有關它的使用信息。在C/C++庫中是否有一個函數可以提供事實性的，或者是否有一個很好的資源，我可以找到它嗎？有沒有更好的方法來找到特定數組的第n個排列？查找並行化C/C++的第n個排列

例如：

陣列[3] = {1，2，3}

factoradicFunc（3） - >圖2，1,3

factoradicFunc（4） - > 2，3，1

等

來源

2015-11-29 Blaise

回答

3

我已經張貼了下面的例子在其他地方，但讓我重複在這裏：

#include <stdlib.h> 
#include <string.h> 
#include <stdio.h> 
#include <errno.h> 

typedef char   element_t; 
typedef unsigned long permutation_t; 

static permutation_t factorial(const permutation_t n) 
{ 
    permutation_t i, result = 1; 
    for (i = 2; i <= n; i++) { 
     const permutation_t newresult = result * i; 
     if ((permutation_t)(newresult/i) != result) 
      return 0; 
     result = newresult; 
    } 
    return result; 
} 

int permutation(element_t *const  buffer, 
       const element_t *const digits, 
       const size_t   length, 
       permutation_t   index) 
{ 
    permutation_t scale; 
    size_t   i, d; 

    if (!buffer || !digits || length < 1) 
     return errno = EINVAL; 

    scale = factorial(length); 
    if (!scale) 
     return errno = EMSGSIZE; 
    if (index >= scale) 
     return errno = ENOENT; 

    /* Copy original ordered set to mutable buffer */  
    memmove(buffer, digits, length * sizeof (element_t)); 

    for (i = 0; i < length - 1; i++) { 
     scale /= (permutation_t)(length - i); 
     d = index/scale; 
     index %= scale; 
     if (d > 0) { 
      const element_t c = buffer[i + d]; 
      memmove(buffer + i + 1, buffer + i, d * sizeof (element_t)); 
      buffer[i] = c; 
     } 
    } 

    return 0; 
}

的factorial()功能僅僅是一個緩慢但謹慎地執行factorial。自13以來！ > 2 ，21！ > 2 和35！ > 2 ，對於32,64或128位無符號整數permutation_t類型，只有很少可能的結果，因此最好僅爲階乘使用數組查找（如rcgldr already mentioned）。

的permutation(buffer, digits, length, index)函數採用長度length的目標buffer，並與digits的index「日排列填充。 （該digits的，不可變的只讀的。）

這不是最快的實現，但它會計算任意排列在O(length)時間複雜度（忽略memmove()操作;如果你考慮到memmove()O(length²)）。它是次優的，因爲它使用memmove()來重新排列目標buffer中的項目，並且每個元素需要兩個除法（並且具有相同除數的一個模）。

考慮最大實際長度的限制（12，20，或34層的元件，這取決於permutation_t類型的大小），使用的memmove()不是問題（因爲數據內的一個或至多幾個緩存行）。

這是線程安全的，只要一個線程同時在同一個目標buffer上運行;多個線程從同一個來源生成不同的目標bufferdigits緩衝區是線程安全的。

來源

2015-11-29 19:58:15

相關問題

 相關問題