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 回答