Вычисление всех подмножеств набора чисел

Question

Я хочу найти подмножества набора целых чисел.Это первый шаг алгоритма «Сумма подмножеств» с возвратом.Я написал следующий код, но он не возвращает правильный ответ:

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, 5
3, 5
5

Я думаю, что проблема в части list.removeAll (list);но я не знаю, как это исправить.

Answer 1

Я действительно пытался решить эту проблему и получил алгоритм @phimuemue из предыдущего поста. Вот то, что я реализовал. Надеюсь, что это работает.

/**
*@Sherin Syriac
*
*/

import java.util.ArrayList;
import java.util.List;

public class SubSet {
    ArrayList<List<Integer>> allSubset = new ArrayList<List<Integer>>();

    /**
     * @param args
     */
    public static void main(String[] args) {
        SubSet subSet = new SubSet();
        ArrayList<Integer> set = new ArrayList<Integer>();
        set.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        subSet.getSubSet(set, 0);
        for (List<Integer> list : subSet.allSubset) {
            System.out.print("{");
            for (Integer element : list) {
                System.out.print(element);
            }
            System.out.println("}");
        }

    }

    public void getSubSet(ArrayList<Integer> set, int index) {
        if (set.size() == index) {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            allSubset.add(temp);
        } else {
            getSubSet(set, index + 1);
            ArrayList<List<Integer>> tempAllSubsets = new ArrayList<List<Integer>>();
            for (List subset : allSubset) {
                ArrayList<Integer> newList = new ArrayList<Integer>();
                newList.addAll(subset);
                newList.add(set.get(index));
                tempAllSubsets.add(newList);
            }

            allSubset.addAll(tempAllSubsets);
        }

    }

}

Answer 2

Вот логика для печати всех подмножеств данного набора чисел.Это также называется powerset набора.Я использовал простой рекурсивный подход для решения этой проблемы с использованием Java, но вы можете соответственно кодировать и на других языках.

import java.util.Scanner;

public class PowerSubset {

    public static void main(String[] args) {

        // HardCoded Input
         int arr[] = { 1, 2, 3 };//original array whose subset is to be found
         int n=3; //size of array

        // Dynamic Input
        /*Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int arr[] = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }*/

        int data[] = new int[arr.length]; // temporary array

        printSubset(arr, data, n, 0, 0);
    }

    public static void printSubset(int arr[], int data[], int n, int dataIndex, int arrIndex) {
        if (arrIndex == n) { //comparing with n since now you are at the leaf node
            System.out.print("[");//watch pictorial chart in the below video link 
            for (int j = 0; j < n; j++) {
                System.out.print(data[j] == 0 ? "" : data[j]);
            }
            System.out.print("]");
            System.out.println();
            return;
        }
        data[dataIndex] = arr[arrIndex];
        printSubset(arr, data, n, dataIndex + 1, arrIndex + 1);//recursive call 1
        data[dataIndex] = 0;
        printSubset(arr, data, n, dataIndex, arrIndex + 1);//recursive call 2
    }

}

Вывод вышеприведенного кода:

[123]
[12]
[13]
[1]
[23]
[2]
[3]
[]

Чтобы получитьКонцепция, которую вы можете посмотреть в следующем видео на YouTube, где четко объясняется, какой подход используется в коде.https://www.youtube.com/watch?v=vEL15C3vbVE

Answer 3

Вот какой-то псевдокод. Одни и те же рекурсивные вызовы можно вырезать, сохраняя значения для каждого вызова по ходу и до проверки рекурсивного вызова, если значение вызова уже присутствует.

В следующем алгоритме будут все подмножества, кроме пустого.

list * subsets(string s, list * v){
    if(s.length() == 1){
        list.add(s);    
        return v;
    }
    else
    {
        list * temp = subsets(s[1 to length-1], v);     
        int length = temp->size();

        for(int i=0;i<length;i++){
            temp.add(s[0]+temp[i]);
        }

        list.add(s[0]);
        return temp;
    }
}