列出所有的k元組的條目求和至n，忽略轉速

是否有發現的ķ非負整數的所有序列，其總和Ñ一種有效的算法，同時避免旋轉（完全，如果可能的話）？順序很重要，但旋轉對於我正在處理的問題是多餘的。列出所有的k元組的條目求和至n，忽略轉速

例如，ķ = 3和Ñ = 3，我想獲得如下所示的列表：

（3，0,0），（2，1,0），（2,0,1），（1,1,1）。

元組（0,3,0）不應該在列表中，因爲它是（3,0,0）的旋轉。但是，（0,3,0）可以在列表而不是（3,0,0）中。請注意，（2,1,0）和（2,0,1）都在列表中 - 我不想避免所有排列的元組，只是旋轉。此外，0是一個有效的條目 - 我不尋找分區n。

我的當前程序是循環從超過1 < = 我 < = Ñ，設定第一條目等於我，然後遞歸地解決問題爲N」 = Ñ - 我和K」 = ķ - 1，我通過強制要求的條目是嚴格大於第一得到一些加速，但這種方法仍然產生大量的旋轉 - 例如，給出ñ = 4和k = 3，（2,2,0）和（2,0,2）都在輸出列表中。

編輯：以粗體添加說明。我很抱歉沒有把這些問題弄清楚，因爲我在原帖中應該有這些問題。

來源

2010-09-16 Seth

你**是**尋找n的分區，但大小**高達** K。並插入零填充k空間 – 2010-09-17 05:39:52

我認爲如果您計算所有總和爲n的無序集合，然後找到所有避免這些集合的旋轉的唯一序列，那麼您會最好。 – 2010-09-17 05:55:25

@belisarius：找到尺寸爲_k_的_n_的所有分區是問題的一部分，但不是全部。嚴格地說，如果加數的順序是置換的，那麼兩個分區是相同的。我沒有計算分區的困難，或者甚至是所有的加數排列 - 問題是找到所有的排列順序。 – Seth 2010-09-17 06:08:11

可以首先生成作爲元組（X_1，X_2，...，x_n）

其中X -1 =次數i發生分區（這完全忽略順序）。

So Sum i * x_i = n。

我相信你已經知道如何做到這一點（來自你的評論）。

一旦你有一個分區，你現在可以爲此生成排列（將其視爲多集{1,1，...，2,2 ...，... n}，其中我出現x_i次），它忽略旋轉，使用回答這個問題：

Is there an algorithm to generate all unique circular permutations of a multiset?

希望有所幫助。

來源

2010-09-17 06:23:38

謝謝！這正是我需要的。 – Seth 2010-09-17 06:45:29

@seth或Aryabhatta，你可以顯示或鏈接到你的算法尋找長度爲k的所有分區，其中每個輪換都很重要嗎？這是其他人需要使用這個答案，我希望我的應用程序的所有輪換。謝謝！ – nealmcb 2014-12-22 01:58:54

您可以對您的解決方案進行排序並消除這種旋轉方式。
OR
你可以嘗試讓你的遞歸解決方案構建僅會進行排序

如何元組？這裏是我快速編寫的東西

static list<tuple> tups; 
void recurse(tuple l, int n, int k, int m) 
{ 
    if (k == 0 && n == 0) 
    { 
    tups.add(l); 
    return; 
    } 
    if (k == 0) 
    return; 

    if (k*m > n) //prunes out tuples that could not possibly be sorted 
    return; 
    else 
    for(int x = m; x <= n; x++) 
     recurse(l.add(x), n-x, k-1, x); //try only tuples that are increasing 
}

用m = 0和初始步驟的空列表調用它。

這裏有一個C＃控制檯應用程序執行：http://freetexthost.com/b0i05jkb4e

哦，我明白我的錯誤在旋轉的假設下，我還以爲你剛纔的意思排列，而不是實際的旋轉。但是，您可以擴展我的解決方案以創建唯一增加的元組的非旋轉排列。我現在正在處理它

來源

2010-09-17 00:11:26

感謝您的回覆。如果我正確地閱讀它，我不認爲「只嘗試增加的元組」是有效的。例如，對於k = 4，n = 6，元組（1,2,1,2）應該是輸出的一部分，但不會增加此元組的旋轉。 – Seth 2010-09-17 00:19:40

您需要按照字典順序生成Integer Partitions。

Here是一個非常好的論文，具有快速算法。

HTH。

請注意CAS programs通常會實現這些功能。例如，在Mathematica：

Innput: IntegerPartitions[10, {3}] 
Output: {{8, 1, 1}, {7, 2, 1}, {6, 3, 1}, 
     {6, 2, 2}, {5, 4, 1}, {5, 3, 2}, 
     {4, 4, 2}, {4, 3, 3}}

來源

2010-09-17 01:21:12

你的答案與Jean有同樣的誤解。 – 2010-09-17 01:36:45

列出所有的k元組的條目求和至n，忽略轉速

回答

相關問題