// 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(0,1) auk veldisfylkis x.substring(0,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;

}