using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

using System.Diagnostics;

namespace Permutations
{
    public partial class frm64Permutations : Form
    {
        public frm64Permutations()
        {
            InitializeComponent();
        }

        // Generate the permutations.
        private void goButton_Click(object sender, EventArgs e)
        {
            // Get the items.
            string[] items = itemsTextBox.Text.Split(' ');

            // Generate the permutations.
            List<List<string>> results =
                GeneratePermutations<string>(items.ToList());

            // Display the results.
            permutationsListBox.Items.Clear();
            foreach (List<string> combination in results)
            {
                permutationsListBox.Items.Add(string.Join(" ", combination.ToArray()));
            }

            // Calculate the number of permutations.
            long numPermutations = Factorial(items.Length);
            numPermutationsTextBox.Text = numPermutations.ToString();

            // Check the result.
            Debug.Assert(permutationsListBox.Items.Count == numPermutations);
        }

        // Generate permutations.
        private List<List<T>> GeneratePermutations<T>(List<T> items)
        {
            // Make an array to hold the permutation we are building.
            T[] currentPermutation = new T[items.Count];

            // Make an array to tell whether an item is in the current selection.
            bool[] inSelection = new bool[items.Count];

            // Make a result list.
            List<List<T>> results = new List<List<T>>();

            // Build the combinations recursively.
            PermuteItems<T>(items, inSelection,
                currentPermutation, results, 0);

            // Return the results.
            return results;
        }

        // Recursively permute the items that are not yet in the current selection.
        private void PermuteItems<T>(List<T> items, bool[] inSelection,
            T[] currentPermutation, List<List<T>> results, int nextPosition)
        {
            // See if all of the positions are filled.
            if (nextPosition == items.Count)
            {
                // All of the positioned are filled.
                // Save this permutation.
                results.Add(currentPermutation.ToList());
            }
            else
            {
                // Try options for the next position.
                for (int i = 0; i < items.Count; i++)
                {
                    if (!inSelection[i])
                    {
                        // Add this item to the current permutation.
                        inSelection[i] = true;
                        currentPermutation[nextPosition] = items[i];

                        // Recursively fill the remaining positions.
                        PermuteItems<T>(items, inSelection,
                            currentPermutation, results, nextPosition + 1);

                        // Remove the item from the current permutation.
                        inSelection[i] = false;
                    }
                }
            }
        }

        // Return n!
        private long Factorial(long n)
        {
            long result = 1;
            for (int i = 2; i <= n; i++) result *= i;
            return result;
        }


        /// <summary>
        /// Required designer variable.
        /// </summary>
        private System.ComponentModel.IContainer components = null;

        /// <summary>
        /// Clean up any resources being used.
        /// </summary>
        /// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>
        protected override void Dispose(bool disposing)
        {
            if (disposing && (components != null))
            {
                components.Dispose();
            }
            base.Dispose(disposing);
        }

        #region Windows Form Designer generated code

        /// <summary>
        /// Required method for Designer support - do not modify
        /// the contents of this method with the code editor.
        /// </summary>
        private void InitializeComponent()
        {
            this.numPermutationsTextBox = new System.Windows.Forms.TextBox();
            this.permutationsListBox = new System.Windows.Forms.ListBox();
            this.label3 = new System.Windows.Forms.Label();
            this.goButton = new System.Windows.Forms.Button();
            this.itemsTextBox = new System.Windows.Forms.TextBox();
            this.label1 = new System.Windows.Forms.Label();
            this.SuspendLayout();
            // 
            // numPermutationsTextBox
            // 
            this.numPermutationsTextBox.Location = new System.Drawing.Point(89, 82);
            this.numPermutationsTextBox.Name = "numPermutationsTextBox";
            this.numPermutationsTextBox.ReadOnly = true;
            this.numPermutationsTextBox.Size = new System.Drawing.Size(50, 20);
            this.numPermutationsTextBox.TabIndex = 24;
            this.numPermutationsTextBox.TextAlign = System.Windows.Forms.HorizontalAlignment.Right;
            // 
            // permutationsListBox
            // 
            this.permutationsListBox.Anchor = ((System.Windows.Forms.AnchorStyles)((((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Bottom) 
            | System.Windows.Forms.AnchorStyles.Left) 
            | System.Windows.Forms.AnchorStyles.Right)));
            this.permutationsListBox.FormattingEnabled = true;
            this.permutationsListBox.IntegralHeight = false;
            this.permutationsListBox.Location = new System.Drawing.Point(13, 108);
            this.permutationsListBox.Name = "permutationsListBox";
            this.permutationsListBox.Size = new System.Drawing.Size(229, 141);
            this.permutationsListBox.TabIndex = 22;
            // 
            // label3
            // 
            this.label3.AutoSize = true;
            this.label3.Location = new System.Drawing.Point(12, 85);
            this.label3.Name = "label3";
            this.label3.Size = new System.Drawing.Size(71, 13);
            this.label3.TabIndex = 21;
            this.label3.Text = "Permutations:";
            // 
            // goButton
            // 
            this.goButton.Anchor = System.Windows.Forms.AnchorStyles.Top;
            this.goButton.Location = new System.Drawing.Point(91, 53);
            this.goButton.Name = "goButton";
            this.goButton.Size = new System.Drawing.Size(75, 23);
            this.goButton.TabIndex = 20;
            this.goButton.Text = "Go";
            this.goButton.UseVisualStyleBackColor = true;
            this.goButton.Click += new System.EventHandler(this.goButton_Click);
            // 
            // itemsTextBox
            // 
            this.itemsTextBox.Anchor = ((System.Windows.Forms.AnchorStyles)(((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Left) 
            | System.Windows.Forms.AnchorStyles.Right)));
            this.itemsTextBox.Location = new System.Drawing.Point(13, 27);
            this.itemsTextBox.Name = "itemsTextBox";
            this.itemsTextBox.Size = new System.Drawing.Size(229, 20);
            this.itemsTextBox.TabIndex = 19;
            this.itemsTextBox.Text = "Ape Bear Cat Dog Elf";
            // 
            // label1
            // 
            this.label1.AutoSize = true;
            this.label1.Location = new System.Drawing.Point(13, 11);
            this.label1.Name = "label1";
            this.label1.Size = new System.Drawing.Size(35, 13);
            this.label1.TabIndex = 18;
            this.label1.Text = "Items:";
            // 
            // frm64Permutations
            // 
            this.AcceptButton = this.goButton;
            this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
            this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
            this.ClientSize = new System.Drawing.Size(254, 261);
            this.Controls.Add(this.numPermutationsTextBox);
            this.Controls.Add(this.permutationsListBox);
            this.Controls.Add(this.label3);
            this.Controls.Add(this.goButton);
            this.Controls.Add(this.itemsTextBox);
            this.Controls.Add(this.label1);
            this.Name = "frm64Permutations";
            this.Text = "Permutations";
            this.ResumeLayout(false);
            this.PerformLayout();

        }

        #endregion

        private System.Windows.Forms.TextBox numPermutationsTextBox;
        private System.Windows.Forms.ListBox permutationsListBox;
        private System.Windows.Forms.Label label3;
        private System.Windows.Forms.Button goButton;
        private System.Windows.Forms.TextBox itemsTextBox;
        private System.Windows.Forms.Label label1;
    }
}