1

文字列のすべてのサブセットを一覧表示するプログラムを作成しています。私のプログラム（以下に示します）は、「abcd」のサブセットを次の順序でリストします。

'' 'd' 'c' 'cd' 'b' 'bd' 'bc' 'bcd' 'a' 'ad' 'ac' 'acd' 'ab' 'abd' 'abc' 'abcd'

どちらが正しい。ただし、参照ソリューションでは、次の順序でリストされています。

'' 'a' 'b' 'ab' 'c' 'ac' 'bc' 'abc' 'd' 'ad' 'bd' 'abd' 'cd' 'acd' 'bcd' 'abcd'

私の質問は次のとおりです。この注文の名前は何ですか?

参考までに、私のプログラムは次のとおりです。

import java.util.ArrayList;
import java.util.Collections;

/**
   This class generates subsets of a string.
*/
public class SubsetGenerator
{
   public static ArrayList<String> getSubsets(String word)
   {
       ArrayList<String> result = new ArrayList<String>();
      //fill out
       //result.add("");
       if(word.length() == 0)
       {

           result.add("");
        }

   else
    {
        String notFirst = word.substring(1);
        ArrayList<String> smaller = getSubsets(notFirst);
        //System.out.println(smaller);
        char first = word.charAt(0);

        result.addAll(smaller);

        for(String i: smaller)
        {
            result.add(first+i);
        }
    }


   //simpleSubsets = getSubsets(simple+word.charAt(0));

  // Form a simpler word by removing the first character
  // fill out

  // Generate all subsets of the simpler word
  // fill out

  // Add the removed character to the front of
  // each subset of the simpler word, and
  // also include the word without the removed character
  // fill out

  // Return all subsets
  return result;
   }
}
4

1 に答える 1

1

彼らが生成している順序は、バイナリでカウントオフし、数字 0 と 1 を a、b、c、および d に変換した場合に得られる順序です。

d c b a | set
--------+----
0 0 0 0 | {}
0 0 0 1 | {a}
0 0 1 0 | {b}
0 0 1 1 | {a, b}
0 1 0 0 | {c}
0 1 0 1 | {a, c}
0 1 1 0 | {b, c}
0 1 1 1 | {a, b, c}
1 0 0 0 | {d}
1 0 0 1 | {a, d}
1 0 1 0 | {b, d}
1 0 1 1 | {a, b, d}
1 1 0 0 | {c, d}
1 1 0 1 | {a, c, d}
1 1 1 0 | {b, c, d}
1 1 1 1 | {a, b, c, d}

お役に立てれば！

于 2013-10-05T23:05:44.543 に答える