EnumRationals

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace EnumPrimes
{
    public struct Rational
    {
        public int Numerator;
        public int Denominator;

        public Rational(int numerator, int denominator)
        {
            this.Numerator = numerator;
            this.Denominator = denominator;
        }

        public override string ToString()
        {
            return Numerator.ToString() + "/" + Denominator.ToString();
        }
    }

    class Program
    {
        [STAThread]
        static void Main(string[] args)
        {
            new Program().DoWork();
        }

        private void DoWork()
        {
            int count = 0;
            var sb = new StringBuilder();
            var set = new HashSet<string>();
            foreach (var i in EnumRationalNumbers())
            {
                var rational = i.ToString();
                sb.AppendLine(rational);
                count++;
                if (!set.Add(rational))
                {
                    throw new Exception("Dupe: " + rational);
                }
            }

            Console.WriteLine(count);
            Clipboard.SetText(sb.ToString());
        }

        const int lower = -3;
        const int upper = 3;
        const int usePrimes = 1000;
        const int slots = 16;
        const int maxFactors = 3;

        public IEnumerable<Rational> EnumRationalNumbers()
        {
            var primes = GetPrimes(usePrimes).ToArray();

            for (int i = 1; i <= maxFactors; i++)
            {
                foreach (int[] intArray in EnumIntArrays3(i))
                {
                    int numerator = 1;
                    int denominator = 1;
                    for (int j = 0; j < intArray.Length; j++)
                    {
                        int exponent = intArray[j];
                        int power = Pow(primes[j], Math.Abs(exponent));
                        if (exponent > 0)
                        {
                            numerator *= power;
                        }
                        else if (exponent < 0)
                        {
                            denominator *= power;
                        }
                    }

                    yield return new Rational(numerator, denominator);
                }
            }
        }

        private IEnumerable<int[]> EnumAllSubsets(int setLength, int subsetSize)
        {
            int[] result = new int[setLength];
            foreach (var nested in Foo(setLength, subsetSize, result))
            {
                yield return result;
            }
        }

        private IEnumerable<int[]> Foo(int n, int k, int[] array)
        {
            if (k == 0 || n == 0)
            {
                yield break;
            }

            if (n - 1 >= k && k > 0)
            {
                array[n - 1] = 0;
                foreach (var nested in Foo(n - 1, k, array))
                {
                    yield return nested;
                }
            }

            array[n - 1] = 1;
            if (k == 1)
            {
                yield return array;
            }

            if (k > 1 && n >= k)
            {
                foreach (var nested in Foo(n - 1, k - 1, array))
                {
                    yield return nested;
                }
            }

            array[n - 1] = 0;
        }

        private IEnumerable<int[]> EnumIntArrays3(int subsetLength)
        {
            int[] result = new int[slots];
            int[] active = new int[subsetLength];
            var subsets = EnumAllSubsets(slots, subsetLength);
            foreach (var subset in subsets)
            {
                int c = 0;
                for (int i = 0; i < subset.Length; i++)
                {
                    if (subset[i] == 1)
                    {
                        active[c++] = i;
                        result[i] = lower;
                    }
                    else
                    {
                        result[i] = 0;
                    }
                }

                for (int i = 0; i < subsetLength; i++)
                {
                    result[active[i]] = lower;
                }

                do
                {
                    yield return result;
                }
                while (Increment2(result, active));
            }
        }

        private bool Increment2(int[] result, int[] active)
        {
            int length = active.Length;
            int last = active[active.Length - 1];
            for (int i = 0; i < length; i++)
            {
                var old = result[active[i]];
                if (old < upper)
                {
                    old++;
                    if (old == 0)
                    {
                        old++;
                    }

                    result[active[i]] = old;
                    return true;
                }
                else
                {
                    result[active[i]] = lower;
                }
            }

            return false;
        }

        private IEnumerable<int[]> EnumIntArrays2(int length)
        {
            int[] result = new int[length];
            foreach (var nested in EnumFoo(result, Math.Min(maxFactors, length)))
            {
                yield return nested;
            }
        }

        private static IEnumerable<int[]> EnumFoo(int[] result, int level)
        {
            for (int j = 0; j < result.Length; j++)
            {
                if (result[j] == 0)
                {
                    for (int k = lower; k <= upper; k += k != -1 ? 1 : 2)
                    {
                        result[j] = k;
                        if (level == 1)
                        {
                            yield return result;
                        }
                        else
                        {
                            foreach (var nested in EnumFoo(result, level - 1))
                            {
                                yield return nested;
                            }
                        }
                    }

                    result[j] = 0;
                }
            }
        }

        private IEnumerable<int[]> EnumIntArrays(int length)
        {
            int last = length - 1;

            int[] result = new int[length];
            for (int i = 0; i < length; i++)
            {
                result[i] = lower;
            }

            do
            {
                yield return result;
            }
            while (Increment(result));
        }

        private bool Increment(int[] result)
        {
            int length = result.Length;
            int last = length - 1;
            for (int i = 0; i < length; i++)
            {
                if (result[i] < upper)
                {
                    result[i]++;
                    if (i == last && result[i] == 0)
                    {
                        result[i]++;
                    }

                    return true;
                }
                else
                {
                    result[i] = lower;
                }
            }

            return false;
        }

        private int Pow(int p, int exponent)
        {
            int result = 1;
            for (int i = 0; i < exponent; i++)
            {
                result *= p;
            }

            return result;
        }

        public IEnumerable<int> GetPrimes(int count)
        {
            int[] result = new int[count];

            for (int i = 2; i < count; i++)
            {
                if (result[i] == 0)
                {
                    yield return i;
                    for (int j = i; j < count; j += i)
                    {
                        result[j] = 1;
                    }
                }
            }
        }
    }
}