做有序排列的有效方式

-2

我不知道它是否可能，但我試圖在C＃中找到一種算法，它可以生成一組數字的所有排列，其中有一些「空白空間」同時保持秩序。做有序排列的有效方式

實施例：

我有一個數組[1,2]和我需要所有所述有序排列有兩個「空空間」。在這種情況下，我將有：

[1,2,null,null] 
[1,null,2,null] 
[1,null,null,2] 
[null,1,2,null] 
[null,1,null,2] 
[null,null,1,2]

我試圖做包括置換前陣內所有的「空的空間」，但它產生太多的排列，我不需要。

在C＃中，函數可能是

private static List<int[]> PermutateWithSpace(this List<int> set, int numberOfEmptySpace) 
    { 
     // Algorithm which yield all possible permutations of my N "null" inside my set 
    }

來源

2017-06-06 KDelli

目前還不清楚算法的定義是什麼。即什麼決定了你有多少空的空間，它只是空蕩蕩的空間而已？在你的例子中'[1，null，null，2]'出現兩次 - 爲什麼算法中的規則描述重複？ – LB2

如果可以的話，往上走一層。你可能不是爲了好玩而這樣做，而是因爲其他一些算法需要它作爲輸入，對吧？有什麼方法可以通過在讀取輸入時根據需要插入'null'來簡單地製作出更聰明的人？至少保存訂單應該更容易。 –

這是[數組排列]（https://stackoverflow.com/questions/2920315/permutation-of-array）中的答案，因爲空值可以被視爲重複字符。只是谷歌「重複生成排列」。 – Dukeling

當然，這算法很簡單。

假設你有n個數字和m個空值。我們將從空值開始，然後插入數字。

我們做的第一件事是找出第一個數字在哪裏。我們產生0,1,2，... m個零點，然後產生第一個數字。

假設我們在這個排列上得到了x個空值。現在我們計算出第二個數字的位置。我們產生0,1,2，... m-x個零點，然後產生第二個數字。

依此類推。

這是足夠的提示，還是你需要看到算法寫出來？

如果您遇到問題：

static IEnumerable<T> Append<T>(this IEnumerable<T> items, T item) 
{ 
    foreach(var i in items) 
     yield return i; 
    yield return item; 
} 

static IEnumerable<IEnumerable<int?>> DoIt(int min, int max, int nulls) 
{ 
    if (min > max) 
     yield return Enumerable.Repeat<int?>(null, nulls); 
    else 
     for(int i = 0; i <= nulls; ++i) 
      foreach(var r in DoIt(min + 1, max, nulls - i)) 
       yield return Enumerable.Repeat<int?>(null, i).Append(min).Concat(r);  
}

，或者甚至更緊湊，在LINQ風格！

static IEnumerable<IEnumerable<int?>> DoIt(int min, int max, int nulls) 
{ 
    return (min > max) ? 
     new[] { Enumerable.Repeat<int?>(null, nulls) } : 
     from i in Enumerable.Range(0, nulls + 1) 
     from r in DoIt(min + 1, max, nulls - i) 
     select Enumerable.Repeat<int?>(null, i).Append(min).Concat(r); 
}

來源

2017-06-06 14:21:44

謝謝！我會嘗試用你的提示編寫一個C＃算法。 – KDelli

工程就像一個魅力！令人難以置信的快速的方式 – KDelli

做有序排列的有效方式

回答

相關問題