矩形的所有獨特組合通過重新排序和翻轉

我們給出N個不同大小的矩形框（允許重複）。編寫一個程序來查找我們可以通過交換順序和翻轉它們來重新排序這些幀的所有獨特方式。矩形的所有獨特組合通過重新排序和翻轉

輸入：

輸出：

12 
(2, 2) | (2, 3) | (2, 3) 
(2, 2) | (2, 3) | (3, 2) 
(2, 2) | (3, 2) | (2, 3) 
(2, 2) | (3, 2) | (3, 2) 
(2, 3) | (2, 2) | (2, 3) 
(2, 3) | (2, 2) | (3, 2) 
(2, 3) | (2, 3) | (2, 2) 
(2, 3) | (3, 2) | (2, 2) 
(3, 2) | (2, 2) | (2, 3) 
(3, 2) | (2, 2) | (3, 2) 
(3, 2) | (2, 3) | (2, 2) 
(3, 2) | (3, 2) | (2, 2)

這裏是我到目前爲止的代碼在C＃：

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace Frames 
{ 
    class Program 
    { 
     static void Main() 
     { 
      var n = int.Parse(Console.ReadLine()); 
      var frames = new Tuple<int, int>[n * 2]; 

      for (int i = 0; i < n * 2; i += 2) 
      { 
       var strs = Console.ReadLine().Split(' '); 
       frames[i] = new Tuple<int, int>(int.Parse(strs[0]), int.Parse(strs[1])); 
       frames[i + 1] = new Tuple<int, int>(frames[i].Item2, frames[i].Item1); 
      } 

      Array.Sort(frames); 

      Recursion(frames, 0, n, new Tuple<int, int>[n], new bool[frames.Length]); 
     } 

     static void Recursion(Tuple<int, int>[] frames, int position, int n, Tuple<int, int>[] current, bool[] used) 
     { 
      if (position == n) 
      { 
       Console.WriteLine(string.Join(" | ", (IEnumerable<Tuple<int, int>>)current)); 
       return; 
      } 

      for (int i = 0; i < frames.Length - 1; i++) 
      { 
       if (used[i]) 
       { 
        continue; 
       } 
       used[i] = true; 
       current[position] = frames[i]; 
       Recursion(frames, position + 1, n, current, used); 
       used[i] = false; 
      } 
     } 
    } 
}

我似乎無法弄清楚如何看待這兩個所使用的框架旋轉，然後排除重複。任何方向將不勝感激。

來源

2017-09-01 Mark Titorenkov

對於你的12個例子，是不是前兩行相同（你剛剛旋轉了第三列90度）？ – mjwills

是的，你可以旋轉和重新排列矩形 –

你能解釋你的輸入是什麼意思嗎？ '3'是什麼意思？那麼'2 3'呢？另外https://betterexplained.com/articles/easy-permutations-and-combinations/可能值得一讀。 https://stackoverflow.com/questions/11208446/generating-permutations-of-a-set-most-efficiently可能是一個起點。 – mjwills

感謝關於哈希集的指示。這是工作解決方案。

using System; 
using System.Collections.Generic; 

namespace Frames 
{ 
    class Program 
    { 
     static SortedSet<string> output = new SortedSet<string>(); 

     static void Main() 
     { 
      var n = int.Parse(Console.ReadLine()); 
      var frames = new Tuple<int, int>[n]; 

      for (int i = 0; i < n; i++) 
      { 
       var strs = Console.ReadLine().Split(' '); 
       frames[i] = new Tuple<int, int>(int.Parse(strs[0]), int.Parse(strs[1])); 
      } 

      Recursion(frames, 0, new Tuple<int, int>[n], new bool[n]); 

      Console.WriteLine(output.Count); 
      Console.WriteLine(string.Join(Environment.NewLine, output)); 
     } 

     static void Recursion(Tuple<int, int>[] frames, int position, Tuple<int, int>[] current, bool[] used) 
     { 
      if (position == frames.Length) 
      { 
       output.Add(string.Join(" | ", (IEnumerable<Tuple<int, int>>)current)); 
       return; 
      } 

      for (int i = 0; i < frames.Length; i++) 
      { 
       if (used[i]) 
       { 
        continue; 
       } 

       used[i] = true; 

       current[position] = frames[i]; 
       Recursion(frames, position + 1, current, used); 

       current[position] = new Tuple<int, int>(frames[i].Item2, frames[i].Item1); 
       Recursion(frames, position + 1, current, used); 

       used[i] = false; 
      } 
     } 
    } 
}

來源

2017-09-01 10:29:17

矩形的所有獨特組合通過重新排序和翻轉

回答

相關問題