/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2008 by Doina Logofatu

in C#: Michael Gärtner
************************************************/


using System;
using System.Collections.Generic;
using System.Collections;
using System.IO;

namespace Logofatu
{
    class P01_DOPI
    {
        private int n;
        private int k;
        private BitArray[] w;
        private int[,] a;
        private int[] p;
        private BitArray b;

        private static Random random = new Random();

        public P01_DOPI(int n, int k)
        {
            this.n = n;
            this.k = k;

            // Wörter generieren
            this.w = new BitArray[n];
            for ( int i = 0; i < n; i++ )
            {
                BitArray wAux = new BitArray(k);
                for ( int j = 0; j < k; j++ )
                {
                    wAux.Set(j, random.Next(2) == 0);
                }
                w[i] = wAux;
            }

            // Aufbau der Matrix
            this.a = new int[n, n];
            for ( int i = 0; i < n; i++ )
            {
                for ( int j = 0; j < n; j++ )
                {
                    a[i, j] = hammingDist(w[i], w[j], k);
                }
            }

            // Initalisierung der Permuatation und des BitStrings
            this.p = new int[n];
            this.b = new BitArray(n);
            for ( int i = 0; i < n; i++ )
            {
                p[i] = i;
                b.Set(i, false);
            }
        }

        // Hamming-Distanz berechnen
        private int hammingDist(BitArray w1, BitArray w2, int size)
        {
            int t = 0;
            for ( int i = 0; i < size; i++ )
                if ( w1[i] != w2[i] )
                    t++;
            return t;
        }

        // Permutation mischen
        private void shufflePermutation()
        {
            for ( int idx = p.Length - 1; idx > 0; idx-- )
            {
                // Wähle einen beliebigen Index zwischen 0 und idx
                int randLoc = random.Next(0, idx + 1);
                int temp = p[randLoc];
                p[randLoc] = p[idx];
                p[idx] = temp;
            }
        }

        // DOP-Kosten für Permutation berechnen
        private int getCostDOP(int[] perm)
        {
            int t = 0;
            for ( int i = 1; i < n; i++ )
                t += a[perm[i - 1], perm[i]];
            return t;
        }

        // DOP-Kosten für vermischte Permutation berechnen
        private int getRandomCostDOP()
        {
            for ( int i = 0; i < n; i++ )
                p[i] = i;
            this.shufflePermutation();
            return getCostDOP(p);
        }

        // DOPI-Kosten für Permutation und BitArray berechnen
        private int getCostDOPI(int[] perm, BitArray bs)
        {
            if ( this.n <= 1 )
                return 0;
            int t = 0;
            for ( int i = 1; i < n; i++ )
                t += bs[i] == bs[i - 1] ? a[perm[i - 1], perm[i]] :
                    k - a[perm[i - 1], perm[i]];
            return t;
        }

        // DOPI-Kosten für zuf. vermischte Permutation und zuf. BitArray berechnen
        private int getRandomCostDOPI()
        {
            for ( int i = 0; i < n; i++ )
            {
                p[i] = i;
                b.Set(i, random.Next(2) == 0);
            }
            this.shufflePermutation();
            return getCostDOPI(p, b);
        }

        // Zwei Elemente eines Arrays vertauschen
        private static void swap(int[] arr, int i, int j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        // Array-Sequenz umkehren
        private static void reverse(int[] arr, int i, int j)
        {
            int half = (i + j - 1) / 2;
            for ( int k = i; k <= half; k++ )
                swap(arr, k, i + j - k);
        }

        // Nachfolger einer Permuation 
        private static bool nextPermuatation(int[] arr)
        {
            int k = arr.Length - 2;
            while ( k >= 0 && arr[k] > arr[k + 1] )
                k--;
            if ( k >= 0 )
            {
                int t = arr.Length - 1;
                while ( arr[t] < arr[k] )
                    t--;
                swap(arr, k, t);
                reverse(arr, k + 1, arr.Length - 1);
                return true;
            }
            else
                return false;
        }

        // DOP: minimale Gesamtkosten für Exakt-Algorithmus (alle Permutationen)
        private int getExactDOP()
        {
            int[] r = new int[n];
            for ( int i = 0; i < n; i++ )
            {
                r[i] = i;
                p[i] = i;
            }
            int t = getCostDOP(p);
            while ( nextPermuatation(r) )
            {
                int aux = getCostDOP(r);
                if ( aux < t )
                {
                    t = aux;
                    Array.Copy(r, 0, p, 0, n);
                }
            }
            return t;
        }

        // Nachfolger eines BitArray
        private static bool nextBitSet(BitArray bs, int numBits)
        {
            int clearBit = nextClearBit(bs, 0);
            if ( clearBit < numBits )
            {
                bs.Set(clearBit, true);
                for ( int i = 0; i < clearBit; i++ )
                    bs.Set(i, false);
                return true;
            }
            else
                return false;
        }

        // DOPI: minimale Gesamtkosten für Exakt-Algorithmus
        // (alle Permutationen und BitArrays)
        private int getExactDOPI()
        {
            int[] r = new int[n];
            for ( int i = 0; i < n; i++ )
            {
                r[i] = i;
                p[i] = i;
            }
            b.SetAll(false);
            int t = getCostDOPI(p, b);
            while ( nextPermuatation(r) )
            {
                BitArray bs2 = new BitArray(n);
                do
                {
                    int aux = getCostDOPI(r, bs2);
                    if ( aux < t )
                    {
                        t = aux;
                        Array.Copy(r, 0, p, 0, n);
                        b.SetAll(false);
                        b.Or(bs2);
                    }
                } while ( nextBitSet(bs2, n) );
            }
            return t;
        }

        // Greedy-Min-Simplified Algorithmus
        int getGMS(bool isDOPI)
        {
            int pIdx = -1;
            b.SetAll(false);
            int bIdx = -1;

            int i0 = 0, j0 = 1;            
            int cost = a[i0, j0];
            for ( int i = 0; i < n - 1; i++ )
            {
                for ( int j = i + 1; j < n; j++ )
                {
                    if ( a[i, j] < cost )
                    {
                        i0 = i;
                        j0 = j;
                        cost = a[i0, j0];
                    }
                    if ( isDOPI && k - a[i, j] < cost )
                    {
                        i0 = i;
                        j0 = j;
                        cost = k - a[i0, j0];
                    }
                }
            }
            p[++pIdx] = i0;
            p[++pIdx] = j0;
            if ( isDOPI )
            {
                b.Set(++bIdx, false);
                b.Set(++bIdx, a[i0, j0] != cost);
            }
            while ( pIdx < n - 1 )
            {
                int next = -1;
                int aux = k + 1;
                for ( int i = 0; i < n ; i++ )
                {
                    bool found = false;
                    for ( int tmpIdx = 0; tmpIdx <= pIdx; tmpIdx++ )
                    {
                        if ( p[tmpIdx] == i )
                        {
                            found = true;
                            break;
                        }
                    }
                    if ( !found )
                    {
                        if ( a[j0, i] < aux )
                        {
                            aux = a[j0, i];
                            next = i;
                        }
                        if ( isDOPI && k - a[j0, i] < aux )
                        {
                            aux = k - a[j0, i];
                            next = i;
                        }
                    }
                }
                p[++pIdx] = next;
                cost +=  aux;
                if ( isDOPI )
                {
                    bool bLast = b[bIdx];
                    b.Set(++bIdx, !(aux == a[j0, next]) ^ bLast);  // logisches XOR
                }
                j0 = next;
            }
            return cost;
        }

        // Greedy-Min Algorithmus
        int getGM(bool isDOPI)
        {
            b.SetAll(false);
            List<int> pAux = new List<int>();
            List<bool> bAux = null;
            bAux = new List<bool>();
            int i0 = 0, j0 = 1;
            int cost = a[i0, j0];
            for ( int i = 0; i < n - 1; i++ )
            {
                for ( int j = i + 1; j < n; j++ )
                {
                    if ( a[i, j] < cost )
                    {
                        i0 = i;
                        j0 = j;
                        cost = a[i0, j0];
                    }
                    if ( isDOPI && k - a[i, j] < cost )
                    {
                        i0 = i;
                        j0 = j;
                        cost = k - a[i0, j0];
                    }
                }
            }
            pAux.Add(i0);
            pAux.Add(j0);
            if ( isDOPI )
            {
                bAux = new List<bool>();
                bAux.Add(false);
                bAux.Add(a[i0, j0] != cost);
            }
            while ( pAux.Count < n )
            {
                int next = -1;
                int aux = k + 1;
                for ( int i = 0; i < n; i++ )
                {
                    int iObj = new int();
                    bool found = false;
                    foreach ( var itPAux in pAux )
                    {
                        if ( itPAux == i )
                        {
                            found = true;
                            iObj = itPAux;                            
                            break;
                        }
                    }
                    if ( !found )
                    {
                        if ( a[j0,i] < aux )
                        {
                            aux = a[j0, i];
                            next = i;
                        }
                        if ( a[i0, i] < aux )
                        {
                            aux = a[i0, i];
                            next = i;
                        }
                        if ( isDOPI && k - a[j0, i] < aux )
                        {
                            aux = k - a[j0, i];
                            next = i;
                        }
                        if ( isDOPI && k - a[i0, i] < aux )
                        {
                            aux = k - a[i0, i];
                            next = i;
                        }
                    }
                }
                cost += aux;
                if ( a[j0, next] == aux || (isDOPI && k - a[j0, next] == aux) )
                {
                    pAux.Add(next);
                    if ( isDOPI )
                    {
                        bAux.Add(!(aux == a[j0, next]) ^ bAux[bAux.Count - 1]);
                    }
                    j0 = next;
                }
                else
                {
                    pAux.Insert(0, next);
                    if ( isDOPI )
                    {
                        bAux.Insert(0, !(aux == a[i0, next]) ^ bAux[0]);
                    }
                    i0 = next;
                }
            }

            for ( int i = 0; i < n; i++ )
            {
                p[i] = pAux[i];
            }
            if ( isDOPI )
            {
                for ( int i = 0; i < n; i++ )
                {
                    b.Set(i, bAux[i]);
                }
            }

            return cost;
        }

        // Multimap für LB-Algorithmus
        private static void putInMultimap(SortedDictionary<int, List<int[]>> mmap, int key, int[] value)
        {
            List<int[]> values = null;
            if ( !mmap.TryGetValue(key, out values) )
            {
                values = new List<int[]>();
                mmap.Add(key, values);
            }
            values.Add(value);
        }

        // Klasse TreeMultimapIterator für LB-Algorithmus
        private class TreeMultimapIterator
        {
            private SortedDictionary<int, List<int[]>>.Enumerator mmapIt;
            private List<int[]>.Enumerator currValuesIt;
            private int[] currValue;
            private KeyValuePair<int, List<int[]>> currEntry;
            private SortedDictionary<int, List<int[]>> mmap;

            public TreeMultimapIterator(SortedDictionary<int, List<int[]>> mmap)
            {
                this.mmap = mmap;
                this.mmapIt = mmap.GetEnumerator();
                mmapIt.MoveNext();
                this.currEntry = this.mmapIt.Current;
                this.currValuesIt = this.currEntry.Value.GetEnumerator();
            }

            public bool next()
            {
                if ( this.currValuesIt.MoveNext() )
                {
                    this.currValue = this.currValuesIt.Current;
                    return true;
                }
                else
                {
                    if ( mmapIt.MoveNext() )
                    {
                        this.currEntry = this.mmapIt.Current;
                        this.currValuesIt = this.currEntry.Value.GetEnumerator();
                        if ( this.currValuesIt.MoveNext() )
                        {
                            this.currValue = this.currValuesIt.Current;
                            return true;
                        }
                        else
                        {
                            return false;
                        }
                    }
                    else
                    {
                        return false;
                    }
                }
            }

            public int Key { get { return this.currEntry.Key; } }

            public int[] Value { get { return this.currValue; } }

            public void remove()
            {
                this.currEntry.Value.Remove(currValue);
                if ( this.currEntry.Value.Count == 0 )
                {
                    this.mmap.Remove(mmapIt.Current.Key);
                }
            }
        }

        // LB Algorithmus (untere Schranke) mit Kruskal Algorithmus
        private int getLB(bool isDOPI)
        {
            int cost = 0;
            SortedDictionary<int, List<int[]>> E = new SortedDictionary<int, List<int[]>>();
            for ( int i = 0; i < n-1; i++ )
            {
                for ( int j = 0; j < n; j++ )
                {
                    int[] e = { i, j };
                    putInMultimap(E, a[i, j], e);
                    if ( isDOPI )                   
                        putInMultimap(E, k - a[i, j], new int[] { i, j });                   
                }
            }
            int[] C = new int[n];
            for ( int i = 0; i < C.Length; i++ )           
                C[i] = i;
            SortedDictionary<int, List<int[]>> H = new SortedDictionary<int, List<int[]>>();
            int szH = 0;
            while ( szH < n - 1 )
            {
                TreeMultimapIterator it = new TreeMultimapIterator(E);
                it.next();
                int uu = it.Value[0];
                int vv = it.Value[1];
                while ( C[uu] == C[vv] )
                {
                    it.next();
                    uu = it.Value[0];
                    vv = it.Value[1];
                }
                putInMultimap(H, it.Key, it.Value);
                szH++;
                cost += it.Key;
                it.remove();
                int mi = Math.Min(C[uu], C[vv]);
                int ma = Math.Max(C[uu], C[vv]);
                for ( int i = 0; i < n; i++ )
                {
                    if ( C[i] == ma )
                    {
                        C[i] = mi;
                    }
                }
            }
            return cost; 
        }


        // Hilfsfunktion: Implementierung nextClearBit für BitArray 
        public static int nextClearBit(BitArray bs, int fromIndex)
        {
            for ( int i = fromIndex; i < bs.Count; i++ )
            {
                if ( !bs[i] )
                    return i;
            }
            return bs.Count;
        }

        // Alle Algorithmen ausführen
        static void Main(string[] args)
        {
            if ( args.Length != 6 )
            {
                throw new IOException("Invalid number of parameters ! Required 6; Provides: " + args.Length);
            }
            int n1 = int.Parse(args[0]);
            int n2 = int.Parse(args[1]);
            int sn = int.Parse(args[2]);
            int k1 = int.Parse(args[3]);
            int k2 = int.Parse(args[4]);
            int sk = int.Parse(args[5]);

            StreamWriter sw = new StreamWriter("report.txt");
            try
            {   
                sw.Write("{0,25}{1,35}\n", " DOP", " DOPI");
                sw.Write("{0,5}{1,5} |{2,5}{3,5}{4,5}{5,5}{6,5} ||" +
                                  "{7,5}{8,5}{9,5}{10,5}{11,5}\n", "n", "k",
                                  "RAN", "EX", "GMS", "GM", "LB",
                                  "RAN", "EX", "GMS", "GM", "LB");

                for ( int n = n1; n <= n2; n += sn )
                {
                    for ( int k = k1; k <= k2; k += sk )
                    {
                        int kk = 3;
                        while ( kk-- > 0 )
                        {
                            P01_DOPI dopi = new P01_DOPI(n, k);
                            sw.Write("{0,5:d}{1,5:d} |", n, k);
                            sw.Write("{0,5:d}{1,5:d}{2,5:d}{3,5:d}{4,5:d} ||",
                                dopi.getRandomCostDOP(), dopi.getExactDOP(),
                                dopi.getGMS(false), dopi.getGM(false), dopi.getLB(false));
                            sw.Write("{0,5:d}{1,5:d}{2,5:d}{3,5:d}{4,5:d}\n",
                                dopi.getRandomCostDOPI(), dopi.getExactDOPI(),
                                dopi.getGMS(true), dopi.getGM(true), dopi.getLB(true));
                        }
                        sw.Write("\n");
                    }
                }                
            }
            finally
            {
                sw.Close();
            }
        }
    }
}