亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

計算一組數字的所有子集

計算一組數字的所有子集

寶慕林4294392 2019-11-13 14:20:14
我想找到一組整數的子集。這是具有回溯功能的“子集總和”算法的第一步。我已經編寫了以下代碼,但是沒有返回正確的答案:BTSum(0, nums);///**************ArrayList<Integer> list = new ArrayList<Integer>();public static ArrayList<Integer> BTSum(int n, ArrayList<Integer> numbers) {    if (n == numbers.size()) {        for (Integer integer : list) {            System.out.print(integer+", ");        }        System.out.println("********************");        list.removeAll(list);        System.out.println();    } else {        for (int i = n; i < numbers.size(); i++) {            if (i == numbers.size() - 1) {                list.add(numbers.get(i));                BTSum(i + 1, numbers);            } else {                list.add(numbers.get(i));                for (int j = i+1; j < numbers.size(); j++)                BTSum(j, numbers);            }        }    }    return null;}例如,如果我要計算set = {1,3,5}的子集,則我的方法的結果是: 1, 3, 5, ******************** 5, ******************** 3, 5, ******************** 5, ******************** 3, 5, ******************** 5, ********************我希望它產生:1, 3, 5 1, 53, 55我認為問題出在零件list.removeAll(list);中。但我不知道如何糾正它。
查看完整描述

3 回答

?
交互式愛情

TA貢獻1712條經驗 獲得超3個贊

您想要的就是Powerset。這是一個簡單的實現:


public static Set<Set<Integer>> powerSet(Set<Integer> originalSet) {

        Set<Set<Integer>> sets = new HashSet<Set<Integer>>();

        if (originalSet.isEmpty()) {

            sets.add(new HashSet<Integer>());

            return sets;

        }

        List<Integer> list = new ArrayList<Integer>(originalSet);

        Integer head = list.get(0);

        Set<Integer> rest = new HashSet<Integer>(list.subList(1, list.size()));

        for (Set<Integer> set : powerSet(rest)) {

            Set<Integer> newSet = new HashSet<Integer>();

            newSet.add(head);

            newSet.addAll(set);

            sets.add(newSet);

            sets.add(set);

        }

        return sets;

    }

我將為您提供一個示例,以說明該算法如何用于的冪集{1, 2, 3}:


移除{1}并執行powerset {2, 3};

移除{2}并執行powerset {3};

移除{3}并執行powerset {};

的冪集{}為{{}};

的冪{3}被3聯合{{}}= { {}, {3} };

的冪{2, 3}被{2}聯合{ {}, {3} }= { {}, {3}, {2}, {2, 3} };

的冪{1, 2, 3}被{1}聯合{ {}, {3}, {2}, {2, 3} }= { {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} }。


查看完整回答
反對 回復 2019-11-13
?
九州編程

TA貢獻1785條經驗 獲得超4個贊

就在底漆你怎么能解決這個問題:


方法1

將號碼列表中的第一個元素

從剩余的號碼列表(即沒有選定號碼列表的號碼列表)生成所有子集=>遞歸!

對于上一步中找到的每個子集,將子集本身以及與在步驟1中選擇的元素連接的子集添加到輸出中。

當然,您必須檢查基本情況,即您的號碼列表是否為空。


方法2

眾所周知,帶有n元素的集合具有2^n子集。因此,您可以算出從0到2^n的二進制數,并將二進制數解釋為相應的子集。請注意,此方法需要一個二進制數,該二進制數必須具有足夠的數字來表示整個集合。


將兩種方法之一轉換為代碼應該不是一個太大的問題。


查看完整回答
反對 回復 2019-11-13
?
蕪湖不蕪

TA貢獻1796條經驗 獲得超7個贊

您的代碼確實令人困惑,沒有解釋。


您可以使用位掩碼進行迭代操作,該位掩碼確定集合中的數字。從0到2 ^ n的每個數字都以其二進制表示形式給出一個唯一的子集,例如


對于n = 3:


i = 5-> 101以二進制形式,選擇第一個和最后一個元素i = 7-> 111以二進制形式,選擇前3個元素


假設有n個元素(n <64,如果n大于64,則將永遠運行該元素)。


for(long i = 0; i < (1<<n); i++){

    ArrayList<Integer> subset = new ArrayList<Integer>();

    for(int j = 0; j < n; j++){

        if((i>>j) & 1) == 1){ // bit j is on

            subset.add(numbers.get(j));

        }

    }

    // print subset

}


查看完整回答
反對 回復 2019-11-13
  • 3 回答
  • 0 關注
  • 662 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號