public class Heimaverkefni5
{

    // Notkun:  b = isInPowerArray(x,i,y);
    // Fyrir:   x er strengur sem inniheldur aðeins stafina
    //          a,b,...,z (enska stafrófið).  Enginn
    //          stafur er endurtekinn í strengnum og
    //          stafirnir eru í stafrófsröð.  Lengd
    //          strengsins er því á bilinu 0..26.
    //          i er hvaða heiltala sem er, y er strengur.
    // Eftir:   b er satt þá og því aðeins að veldisfylki
    //          strengsins x hafi strenginn y í sæti i.

    static public boolean isInPowerArray( String x, int i, String y )
    {
        // skilyrði er að 0<=i
        if ((i<0) )
        {
            return false;
        }


        // Það eru vandamál með að x.charAt(0) fyrir núllstrenginn svo við meðhöndlum hann sérstaklega.
        if (y == "")
        {
            // Núllstrengurinn er alltaf í núllta sæti.
            if (i == 0)
            {
            return true;
            }
            return false;
        }



        // ATH!  a == b gáir hvort a og b séu sami hluturinn,   a.equals(b) gáir hvort a og b hafi sama gildi

        // það vantar núllstrenginn í Power(x), það byrjar á "a" svo indexið hliðrast um 1
        if (Power(x)[i-1].equals(y))
        {
            return true;
        }

        // else
        return false ;





    }


    // Notkun: a = Power(x);
    // Fyrir:  x er strengur sem inniheldur stafi
    //         a..z í stafrófsröð, núll eða fleiri.
    //         Hver stafur má í mesta lagi koma fyrir
    //         einu sinni.
    // Eftir:  a vísar á veldisfylki strengsins x, að núllstrengnum undanskildnum. length.a == 2^(x.length())-1



    // Fallið er endurkvæmt og byggir á eftirfarandi staðreynd:
    // Veldisfylki x = fylkið sem inniheldur fremsta staf x bætt við sérhvert stak í veldisfylki x.substring(1) auk veldisfylkis x.substring(1)
    // t.d. er  P(c) = {c, ""}
    //          P(bc) = {bc, b} auk {c, ""}
    //          P(abc) = {a, ab, ac, abc} auk {b, bc, c, ""}
    // Það er skemmtilegt við þessa aðferð er að stökin koma út í stafrófsröð.

    static public String[] Power( String x )
    {
        // Hvað gerist ræðst alfarið af því hversu langur strengurinn x er
        int k = x.length();
        // Grunnur. Fallið verður að taka eitthvað grunngildi. dæmi: Power(abc) kallar á Power(bc) sem loks kallar á Power(c) sem skilar {c}
        // Ath. það er ekki það sama og veldisfylki "c" því tómi strengurinn er ekki með í úttakinu. En það er ekki vandamál.
        if (k == 1)
        {
            String[] res1 = {x};
            return res1;
        }



        int m = (int)Math.pow(2,k) ;  // fjöldi staka í veldisfylkinu P(x)
        int s = (int)Math.pow(2,k-1); // fjöldi staka í P(x.substring(1))
        String[] res = new String[m-1]; // hlöðum gildunum inn í 2^k-1 staka fylki sem verður úttakið (result)
        String x0 = Character.toString(x.charAt(0)); // Fremsti stafurinn í x, sem þarf að vinna sérstaklega með. ath. Munur er á staf og strengnum sem inniheldur stafinn
        String[] substr = Power(x.substring(1));  // köllum á fallið fyrir substrenginn bara einu sinni.  Ef þetta er gert inni í lykkjunum kemur timeout!


        res[0] = x0;  // Þar sem við vinnum ekki með tóma strenginn þarf að setja fremsta stafinn inn í fylkið í hverju skrefi.
                      // Til að finna veldisfylkið viljum við skeyta x0 við öll stök veldisfylkis x.substring(1), en Power(x) inniheldur aldrei tóma strenginn.
                      // Dæmi: P(bc) inniheldur b því "b" + "" == "b"


        // Það eru 2^k = 2^(k-1)+2^(k-1) stök í veldisfylkinu.
        // Helmingur stakanna í veldisfylkinu P(x) eru fremsti stafurinn í x skeyttur saman við sérhvert stak P(x.substring(1))
        // 1 <= i < 2^(k-1)
        for(int i = 1; i < s;  i++)
        { // Fastayrðing lykkju:  res[i-1] er i-ta stak (talið frá 0) veldisfylkisins P(x).

          // ath. fastayrðingin segir til um ástandið eftir að i hefur fengið  gildi fyrir umferðina en áður en nokkuð gerist

          // dæmi: x = "abc", i = 3,  res[i-1] = "abc"
          // P(x) = {"", "a", "ab", "abc", "ac, "b", "bc", "c"}     P(x.substring(1)) = {"", "b", "bc", "c"}
          // i = 1,  res[i-1] = "a"

            res[i] = x0 + substr[i-1];  // Byrjum á 0. staki substrengsins

        }


        // Hinn helmingurinn eru stökin úr P(x.substring(1))
        // 2^(k-1) <= j < 2^k
        for(int j = s; j< m-1 ; j++)
        { // Fastayrðing lykkju: res[j-1] er j-ta stak P(x).

          // dæmi: x = "abc", j = 4,  res[j-1] = "ac"
          // P(x) = {"", "a", "ab", "abc", "ac, "b", "bc", "c"}     P(x.substring(1)) = {"", "b", "bc", "c"}
          // j = 6, res[j-1] = b
            res[j] = substr[ j-s ]; // Byrjum á 0. staki substrengsins

        }


        return res;

    }

}