1

[宿題]

Java または C++ を使用して、特定の集合の累乗集合を見つける必要があります。セットは任意のサイズの配列の形式で受け入れられ、そのセットの累乗セットの要素を表示する必要があります。使用する概念は、配列、ループ、および関数 (再帰的および反復的) のみであることに注意してください。

適用できるロジックに関して、正しい方向に向けてくれる人が必要です。助けてください。

PS : 集合 A の冪集合は、集合 A のすべての部分集合の集合です。A = { a, b, c} A のベキ集合 = {{},{a},{b},{c},{a,b},{b,c},{a,c},{a 、紀元前}}

編集：

「wy」と「MrSmith42」に感謝します！彼らが与えたロジックを使ってプログラムを書きました。今、私はそれを最適化しようとしています。私はJavaが初めてで、その新しさのために少し不快であることに注意してください。

これが私のコードです:

import java.util.Scanner;

public class PowerSet {

    //Function to increment binary string...

    static String incr_bin (String binary){
        char bin[] = new char[100];
        int size_bin, i;
        size_bin = binary.length();
        bin = binary.toCharArray(); 
        bin[size_bin-1]++;
        for(i=size_bin-1; i>=0; i--){
            if (i != 0){
                if(bin[i] > '1'){
                    bin[i]='0';
                    bin[i-1]++;
                }
            }
        }
        if (bin[0]>'1'){
            for(i=0;i<size_bin;i++){
                bin[i]='0';
            }
        }
        binary = new String (bin);
        return binary;
    }



    public static void main(String[] args) {

        //Declarations

        Scanner in = new Scanner (System.in);
        int a[] = new int [100];
        int size_a, i, count=0;

        String binary;

        //Input

        System.out.println("Enter the number of elements in A : ");
        size_a = in.nextInt();
        char bin[] = new char [size_a];
        System.out.println("Enter the elements in A : ");
        for(i=0; i<size_a; i++){
            a[i] = in.nextInt();
            bin[i] = '0';
        }
        binary = new String(bin);

        //Calculating and Setting up subsets
        System.out.println("MEMBERS OF POWER SET :");
        do{
            System.out.print("\n{.");
            count = 0;
            binary = incr_bin(binary);
            bin = binary.toCharArray();
            for(i=0; i<size_a; i++){
                if (bin[i] == '0') count++;
                if (bin[i] == '1') System.out.print(a[i] + "  ");
            }
            System.out.println("}");
        }while(count!=size_a);      
    }
}
4

4 に答える 4

9

累乗セットのすべての要素を、セットのサイズと同じビット数の 2 進数にマップできます。

例えば

     A = { a, b, c} 
     binary number  => resulting subset
     000            => {     }  // no 'a',  no 'b', no 'c'
     001            => {    c}
     010            => {  b  }
     011            => {  b,c}
     100            => {a    }
     101            => {a,  c}
     110            => {a,b  }
     111            => {a,b,c}
于 2013-08-27T13:26:45.090 に答える
0

これがJavaでの実装です。これは、ビットを使用して上記で説明したロジックを使用します。

/**
 * Prints all subsets of a list
 * @param list
 */
public static void printSubsets(List<Integer> list) {
    int max = (int)Math.pow(2, list.size());

    for (int i = 0; i < max; i++) {
        // Convert int to bitset
        BitSet bs = getConvertedBitSet(i, list.size());

        // Use bitset to print the subset
        printSubset(bs, list);
    }
}

/**
 * Helper function for {@link org.vikastaneja.companies.Expedia#printSubsets(java.util.List)}<br/>
 * This function prints the subsets for the bits that are set in bitset
 * @param bs
 * @param list
 */
private static void printSubset(BitSet bs, List<Integer> list) {
    if (list == null) {
        throw new NullPointerException("Set is empty");
    }

    System.out.print("{ ");
    for (int i = 0; i < list.size();i++) {
        if (bs.get(i)) {
            System.out.print(list.get(i) + " ");
        }
    }

    System.out.print("}");

    System.out.println();
}

/**
 * Helper function for {@link org.vikastaneja.companies.Expedia#printSubsets(java.util.List)}<br/>
 * This function converts an integer to the bitset
 * @param value
 * @param size
 * @return
 */
private static BitSet getConvertedBitSet(int value, int size) {
    BitSet bits = new BitSet(size);
    bits.set(0, size - 1, false);
    int index = 0;
    while (value != 0) {
        if (value % 2 != 0) {
            bits.set(index);
        }
        ++index;
        value = value >>> 1;
    }
    return bits;
}
于 2014-07-24T07:36:57.050 に答える