C＃中的置換算法

我正在努力應對這個我需要寫的算法。我正在使用C＃。C＃中的置換算法

說我有一個List<Bag>，我有一個List<Lunch>。我需要編寫一個算法來枚舉所有行李中的所有午餐排列。

例如，假設有3次午餐和2袋：

// Permutation 1 
Bag 1, Lunch 1 
Bag 2, Lunch 1 

// Permutation 2 
Bag 1, Lunch 1 
Bag 2, Lunch 2 

// Permutation 3 
Bag 1, Lunch 1 
Bag 2, Lunch 3 

// Permutation 4 
Bag 1, Lunch 2 
Bag 2, Lunch 1 

// Permutation 5 
Bag 1, Lunch 2 
Bag 2, Lunch 2 

// Permutation 6 
Bag 1, Lunch 2 
Bag 2, Lunch 3 

// Permutation 7 
Bag 1, Lunch 3 
Bag 2, Lunch 1 

// Permutation 8 
Bag 1, Lunch 3 
Bag 2, Lunch 2 

// Permutation 9 
Bag 1, Lunch 3 
Bag 2, Lunch 3

兩個排列Bag 1 Lunch 1 and Bag 2 Lunch 2和Bag 1 Lunch 2 and Bag 2 Lunch 1是不同的，因爲包包有不同的能力，因此，他們將都需要加以列舉。

行李和午餐的數量可以是任意數量。

我創建了一個名爲BagLunch的課程，其中包含一對袋子和午餐。上面給出的示例列表將存儲在List<BagLunch>中。

謝謝。

來源

2012-02-06 user1002358

我不明白你的例子。有幾行列出了'Bag 1，Lunch 1'。排列中有重複的規則是什麼？ – 2012-02-06 22:28:13

對不起，我添加了間距。每個組都是一個排列組合。 – user1002358 2012-02-06 22:29:09

那些不是排列組合.. – duedl0r 2012-02-06 22:31:37

所以你想在n（k =行李箱，n =午餐）的同時保持訂單嗎？我希望你可以假設k < = n，否則你會被卡在空袋子裏...

我不想完全破壞你的功課，所以我只是指着你在右邊方向。這要求遞歸。首先爲第一包選擇午餐，然後選擇剩下的k-1包的午餐。當你只剩下一個包時，選擇其餘的午餐，直到完成。

編輯：

哦，午餐可以一次住在兩個袋子。所以這是n^k。最簡單的方法是使用上面提到的LINQ交叉連接，但這有點像作弊。相反，只需創建一個K元素的整數數組，並用零填充，然後開始向最右邊的元素添加一個元素。當它到達N時，將其重置爲零並將其移到下一個元素。你只需要計算base-N中的K位數字。每次迭代後，您都可以輸出包分配。

來源

2012-02-06 22:31:45 zmbq

是的，這不是作業... – user1002358 2012-02-06 22:32:30

在這個例子中，午餐是可替換的 - 它們可以用在多個包中。 – 2012-02-06 22:36:59

沒錯。我可以有10袋和1頓午餐。在這種情況下，只有1個排列組合：所有10個袋子都包含午餐1. – user1002358 2012-02-06 22:42:06

如果您允許傻瓜[午餐可以在兩個袋子] - 如示例所示，您有#bags^#lunches的可能性。

每個包都有自己獨特的「選擇」，放入午餐即可
爲了生成這些可能性 - 只需「選擇」一個包的午餐，並遞歸地調用算法。重複每個午餐。

生成它們的僞代碼：

generateAll(bags,lunches,sol): 
    if (bags is empty): 
     print sol 
     return 
    bag <- bags.first 
    bags.remove(bag) 
    for each lunch in lunches: 
    sol.append(BagLunch(bag,lunch) 
    generateAll(bags,lunches,sol) 
    sol.removeLast()

來源

2012-02-06 22:31:51 amit

使用交叉聯接在LINQ：

var qry = from bag in bags 
      from lunch in lunches 
      select new BagLunch 
      { Bag=bag, Lunch=lunch}; 
var baglunches = qry.ToList();

編輯：
你要修改的選擇條款來處理結構你的BagLunch類。

來源

2012-02-06 22:33:29 Randolpho

好答案; OP然後必須將結果按'包'分組，然後將這些組相互交叉加入。 – 2012-02-06 22:39:03

我是LINQ的新手，但我只是運行你的例子。它給出了與嵌套的'for'或'foreach'相同的結果：'B1L1，B1L2，B1L3，B2L1，B2L2，B2L3'。這不是我所需要的：（ – user1002358 2012-02-06 22:40:09

這會工作，但它有點像作弊，即使這不是作業 – zmbq 2012-02-06 22:41:50

我有一個方法，重新創建上面的示例。這種方法實際上是把這些袋子當作一個數字的位置......因爲如果你看看你的例子，你可以把它看作11,12,13,21,22,23。那麼這是一個轉化爲基礎Lunch.Count的問題。另外我偷了一個方法從這裏：https://stackoverflow.com/a/95331/483179轉換爲任何基地，它被提及它沒有經過測試，所以你可能不得不建立更強大的東西。最後，我沒有做任何邊緣條件測試，因此喂入0袋可能會有意想不到的結果。這是我想出來的。

class Program 
{ 
    static List<Bag> bags = new List<Bag>(); 
    static List<Lunch> lunches = new List<Lunch>(); 

    static void Main(string[] args) 
    { 
     lunches.Add(new Lunch() { Num = 1 }); 
     lunches.Add(new Lunch() { Num = 2 }); 
     lunches.Add(new Lunch() { Num = 3 }); 
     bags.Add(new Bag() { Num = 1 }); 
     bags.Add(new Bag() { Num = 2 }); 

     int count = 0; 
     while (count < Math.Pow(lunches.Count, bags.Count)) 
     { 
      Console.WriteLine("Permutation " + count); 
      string countNumber = ConvertToBase(count, lunches.Count).PadLeft(bags.Count,'0'); 
      for (int x = 0; x < bags.Count; x++) 
      { 
       Console.WriteLine(bags[x] + " " + lunches[Convert.ToInt32((""+countNumber[x]))]); 

      } 
      Console.WriteLine(""); 
      count++; 
     } 
     Console.ReadLine(); 

    } 

    static string ConvertToBase(int value, int toBase) 
    { 
     if (toBase < 2 || toBase > 36) throw new ArgumentException("toBase"); 
     if (value < 0) throw new ArgumentException("value"); 

     if (value == 0) return "0"; //0 would skip while loop 

     string AlphaCodes = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; 

     string retVal = ""; 

     while (value > 0) 
     { 
      retVal = AlphaCodes[value % toBase] + retVal; 
      value /= toBase; 
     } 

     return retVal; 
    } 

} 

class Lunch 
{ 
    public int Num { get;set;} 
    public override string ToString() 
    { 
     return "Lunch " + Num; 
    } 

} 
class Bag 
{ 
    public int Num { get;set;} 

    public override string ToString() 
    { 
     return "Bag " + Num; 
    } 
}

和結果輸出：

Permutation 0 
Bag 1 Lunch 1 
Bag 2 Lunch 1 

Permutation 1 
Bag 1 Lunch 1 
Bag 2 Lunch 2 

Permutation 2 
Bag 1 Lunch 1 
Bag 2 Lunch 3 

Permutation 3 
Bag 1 Lunch 2 
Bag 2 Lunch 1 

Permutation 4 
Bag 1 Lunch 2 
Bag 2 Lunch 2 

Permutation 5 
Bag 1 Lunch 2 
Bag 2 Lunch 3 

Permutation 6 
Bag 1 Lunch 3 
Bag 2 Lunch 1 

Permutation 7 
Bag 1 Lunch 3 
Bag 2 Lunch 2 

Permutation 8 
Bag 1 Lunch 3 
Bag 2 Lunch 3

來源

2012-02-06 23:26:04 deepee1

C＃中的置換算法

回答

相關問題