using System;
using System.Collections.Generic;
using System.Linq;
 
namespace Permutations
{
    class FloydPermutation
    {
        public static void Main(string[] args)
        {
            RunTest(1, 4);
            RunTest(2, 4);
            RunTest(3, 4);
            RunTest(4, 4);
        }
 
        private static void RunTest(int count, int max)
        {
            var random = new Random(7);
            var samples = Enumerable.Range(0, 100000)
                .Select(_ => GetSample(count, max, random))
                .Select(sample => string.Join(", ", sample.Select(x => x.ToString()).ToArray()))
                .GroupBy(sample => sample)
                .ToArray();
            Console.WriteLine("{0} distinct samples of size {1} chosen from [1,{2}]", samples.Length, count, max);
            foreach (var grouping in samples.OrderBy(sample => sample.Key))
            {
                Console.WriteLine("[{0}]: {1}", grouping.Key, grouping.Count());
            }
        }
 
        private static int[] GetSample(int count, int max, Random random)
        {
            var seen = new Dictionary<int, LinkedListNode<int>>();
            var result = new LinkedList<int>();
            for (var i = max - count + 1; i <= max; i++)
            {
                var t = random.Next(1, i + 1);
                LinkedListNode<int> node;
                if (seen.TryGetValue(t, out node))
                {
                    seen[i] = result.AddAfter(node, i);
                }
                else
                {
                    seen[t] = result.AddFirst(t);
                }
            }
 
            return result.ToArray();
        }
    }
}
 

dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKdXNpbmcgU3lzdGVtLkxpbnE7CgpuYW1lc3BhY2UgUGVybXV0YXRpb25zCnsKICAgIGNsYXNzIEZsb3lkUGVybXV0YXRpb24KICAgIHsKICAgICAgICBwdWJsaWMgc3RhdGljIHZvaWQgTWFpbihzdHJpbmdbXSBhcmdzKQogICAgICAgIHsKICAgICAgICAgICAgUnVuVGVzdCgxLCA0KTsKICAgICAgICAgICAgUnVuVGVzdCgyLCA0KTsKICAgICAgICAgICAgUnVuVGVzdCgzLCA0KTsKICAgICAgICAgICAgUnVuVGVzdCg0LCA0KTsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIHZvaWQgUnVuVGVzdChpbnQgY291bnQsIGludCBtYXgpCiAgICAgICAgewogICAgICAgICAgICB2YXIgcmFuZG9tID0gbmV3IFJhbmRvbSg3KTsKICAgICAgICAgICAgdmFyIHNhbXBsZXMgPSBFbnVtZXJhYmxlLlJhbmdlKDAsIDEwMDAwMCkKICAgICAgICAgICAgICAgIC5TZWxlY3QoXyA9PiBHZXRTYW1wbGUoY291bnQsIG1heCwgcmFuZG9tKSkKICAgICAgICAgICAgICAgIC5TZWxlY3Qoc2FtcGxlID0+IHN0cmluZy5Kb2luKCIsICIsIHNhbXBsZS5TZWxlY3QoeCA9PiB4LlRvU3RyaW5nKCkpLlRvQXJyYXkoKSkpCiAgICAgICAgICAgICAgICAuR3JvdXBCeShzYW1wbGUgPT4gc2FtcGxlKQogICAgICAgICAgICAgICAgLlRvQXJyYXkoKTsKICAgICAgICAgICAgQ29uc29sZS5Xcml0ZUxpbmUoInswfSBkaXN0aW5jdCBzYW1wbGVzIG9mIHNpemUgezF9IGNob3NlbiBmcm9tIFsxLHsyfV0iLCBzYW1wbGVzLkxlbmd0aCwgY291bnQsIG1heCk7CiAgICAgICAgICAgIGZvcmVhY2ggKHZhciBncm91cGluZyBpbiBzYW1wbGVzLk9yZGVyQnkoc2FtcGxlID0+IHNhbXBsZS5LZXkpKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBDb25zb2xlLldyaXRlTGluZSgiW3swfV06IHsxfSIsIGdyb3VwaW5nLktleSwgZ3JvdXBpbmcuQ291bnQoKSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIGludFtdIEdldFNhbXBsZShpbnQgY291bnQsIGludCBtYXgsIFJhbmRvbSByYW5kb20pCiAgICAgICAgewogICAgICAgICAgICB2YXIgc2VlbiA9IG5ldyBEaWN0aW9uYXJ5PGludCwgTGlua2VkTGlzdE5vZGU8aW50Pj4oKTsKICAgICAgICAgICAgdmFyIHJlc3VsdCA9IG5ldyBMaW5rZWRMaXN0PGludD4oKTsKICAgICAgICAgICAgZm9yICh2YXIgaSA9IG1heCAtIGNvdW50ICsgMTsgaSA8PSBtYXg7IGkrKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgdmFyIHQgPSByYW5kb20uTmV4dCgxLCBpICsgMSk7CiAgICAgICAgICAgICAgICBMaW5rZWRMaXN0Tm9kZTxpbnQ+IG5vZGU7CiAgICAgICAgICAgICAgICBpZiAoc2Vlbi5UcnlHZXRWYWx1ZSh0LCBvdXQgbm9kZSkpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgc2VlbltpXSA9IHJlc3VsdC5BZGRBZnRlcihub2RlLCBpKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBzZWVuW3RdID0gcmVzdWx0LkFkZEZpcnN0KHQpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CgogICAgICAgICAgICByZXR1cm4gcmVzdWx0LlRvQXJyYXkoKTsKICAgICAgICB9CiAgICB9Cn0K