java - 这些子集的排列顺序是什么？

Question

我正在编写一个程序来列出一个字符串的所有子集。我的程序(如下所示)按以下顺序列出了“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;
   }
}

Answer 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}

希望这对您有所帮助!