All unique combinations of rectangles by reordering and flipping

Question

We are given N rectangular frames of different sizes (duplicates are allowed). Write a program to find all unique ways we can reorder these frames by exchanging their order and flipping them.

Input:

Output:

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)

Here is my code so far in 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;
            }
        }
    }
}

I can't seem to figure out how to treat both rotations of the frame as used and then exclude duplicates. Any directions would be appreciated.

For your 12 example, aren't the first two rows the same (you have just rotated the third column 90 degrees)? — mjwills, Sep 01 '17 at 09:44
Can you explain what your inputs mean? What does `3` mean? What about `2 3`? Also https://betterexplained.com/articles/easy-permutations-and-combinations/ may be worth a read. https://stackoverflow.com/questions/11208446/generating-permutations-of-a-set-most-efficiently may be a starting point. — mjwills, Sep 01 '17 at 09:46
3 is the number of rectangles (frames) and on each line you get the sizes of the two sides of the frames. And thank you for the article I'll have a look — Mark Titorenkov, Sep 01 '17 at 09:47
For eliminating duplicates, **1)** build up a `List` and use a distinct on it. **2)** keep a `HashSet` with combinations made and check before presenting a 'new' one. — Jeroen van Langen, Sep 01 '17 at 09:55
Yeah I guess this is an option since the Memory Limit for this task is quite high at 45MB — Mark Titorenkov, Sep 01 '17 at 09:57

Mark Titorenkov · Accepted Answer · 2017-09-01T12:32:38.480

Thanks for the directions about the hashset. Here is the working solution.

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;
            }
        }
    }
}

All unique combinations of rectangles by reordering and flipping

1 Answers1