1

特定のセットのすべてのサブセットを計算するこの単純なプログラムがあります。

アルゴリズムは正しいと思います。ただし、一部：

while (included.size()>0){
    ArrayList<Integer> temp =included.remove(0);
    temp.add(first_element);
    output.add(temp);
}

ステートメントtemp.add(first_element)が不必要に not_included を更新しています。理由を理解するのを手伝ってください。

public class Recursion {

    public static ArrayList<ArrayList<Integer>> getSubsets (ArrayList<Integer> input_set){
        ArrayList<ArrayList<Integer>> output=new ArrayList<ArrayList<Integer>>();

        if (input_set.isEmpty()){
            ArrayList<Integer> this_subset=new ArrayList<Integer>();
            output.add(this_subset);
        }      
        else if (input_set.size()==1){
            ArrayList<Integer> empty_subset=new ArrayList<Integer>();
            output.add(input_set);
            output.add(empty_subset);
        }
        else{
            int first_element=input_set.remove(0);
            ArrayList<ArrayList<Integer>> included = getSubsets(input_set);
            ArrayList<ArrayList<Integer>> not_included = getSubsets(input_set);

            while (included.size()>0){
                ArrayList<Integer> temp =included.remove(0);
                temp.add(first_element);
                output.add(temp);
            }
            while (not_included.size()>0){
                output.add(not_included.remove(0));
            }
        }
        return output;
    }


    public static void main(String[] args) {
        ArrayList<Integer> test= new ArrayList<Integer> ();
        test.add(2);
        test.add(1);
        System.out.print(getSubsets(test));
    }
}
4

1 に答える 1

1

試す

ArrayList<ArrayList<Integer>> not_included = getSubsets(input_set.clone());

ただし、配列リストのジェネリック型も配列リストであるため、これはまだ機能しない可能性があります。「ディープ コピー」を検索して、100% 有効なソリューションを見つけてください。

getSubSet は、パラメーターが同じであるため、同じリストへのポインターのみを返します。これが、included と not_included が同じリストである理由です。

于 2013-03-01T00:12:25.723 に答える