0

各要素が [0 ... K] の値を持つことができ、すべての要素の合計が SUM である、長さ N のすべてのベクトルを列挙したいと考えています。

再帰関数を使用してこの問題を解決しましたが、CUDA CI で再入力すると、CUDA C は再帰関数をサポートしていないというメッセージが表示されました。この後、再帰を使用せずにいくつかの変更を加えて関数を書き直しましたが、関数はブール値であり、これも CUDA C ではサポートされていません。これは、他の関数を呼び出さずにメインのグローバル関数を無効にする必要があるためです。今、私はアイデアがありません。

再帰関数は次のとおりです。

    private static void computeVectors(int[] n, int sum, int k, int k1, int i) {


        if (sum == 0) {

            printVectors(n, n.length);
        } else if (i < n.length) {

            for (int j = k; j >= 0; j--) {

                if (j <= k1) {
                    n[i] = j;
                    computeVectors(n, sum - j, sum - j, k1, i + 1);
                }
            }
        }
    }

    private static void printVectors(int p[], int n) {

        for (int i = 0; i < n; i++) {
            System.out.print(p[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {

        // TODO code application logic here
        computeVectors(new int[4], 5, 3, 3, 0);

    }

この例の出力は次のとおりです。

3200 3110 3101 3020 3020 3011 3002 2300 2210 2201 2120 2111110220220202020202020202021200313101301 1220 1211 1211 1202 1130 1121 1112 1103 1031 1022 1013 0320 0311 0302 0230 0221 0212 0203 0131 0131 0122 0122 0122 011332222

0023

4

2 に答える 2

2

CUDA は__device__、Compute Capability (CC) 2.0 以降を搭載したデバイスで再帰関数をサポートします。GPU に CC 2.0 以降が搭載されていることを確認し、それ以降-arch=sm_20(またはそれ以降) でコンパイルする必要があります。

__global__カーネル関数は、 CUDA Dynamic Parallelismを使用して他のカーネルから起動できます。これには CC >= 3.5 が必要です。

いずれにせよ、パフォーマンス上の理由から、おそらく非再帰的なバージョンを作成したいと思うでしょう。

于 2013-08-16T02:44:17.863 に答える
1

これは非再帰的なバージョンです。sum基本的な考え方は、最大でkからの置換でサイズの組み合わせを選択したいということです{0,...,N-1}。次に、要素が選択された回数により、結果のベクトル内のその要素のサイズが決まります。スタートとバーの観点から考えると、sumスターとN-1バーがあります。バーは星をビンに分けます。i番目のビンの星の数はエントリのサイズですi(これは、バーが最大kでも互いに離れている可能性があることを意味します)。必要に応じてバーを左から右に移動すると、例の逆の出力が得られます。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

class Combinations {
    public static void main(String... ignore) {
        int n = 4;
        int sum = 5;
        int k = 3;
        Integer[] set = new Integer[n];
        fillIncreasing(set,0,0,n);

        computeVectors(set,sum,k);
    }

    private static void fillIncreasing(Integer[] array,int from,int first,int to) {
        for ( int i = from ; i < to ; i++ ) {
            array[i] = i-from+first;
        }
    }

    public static void computeVectors(Integer[] set,int size,int maxChoose) {
        int[] vectorToPrint = new int[set.length];
        for ( List<Integer> vector : combinationsWithReplacement(set,size,maxChoose) ) {
            Arrays.fill(vectorToPrint,0);
            for ( Integer entry : vector ) {
                vectorToPrint[entry]++;
            }
            System.out.println("vector: "+Arrays.toString(vectorToPrint));
        }
    }

    public static <T> Iterable<List<T>> combinationsWithReplacement(final T[] set,final int size,final int maxChoose) {
        if ( set.length < 2 ) {
            throw new IllegalArgumentException();
        }
        return new Iterable<List<T>>() {
            public Iterator<List<T>> iterator() {
                return new Iterator<List<T>>() {
                    Integer[] barSpots = new Integer[set.length+1];
                    {
                        fillIncreasing(barSpots,0,0,barSpots.length-1);
                        barSpots[barSpots.length-1] = size+set.length;
                        while ( hasNext() && !readyToReturn() ) {
                            advance();
                        }
                    }
                    private boolean readyToReturn() {
                        if ( ! hasNext() || set.length*maxChoose < size ) {
                            return false;
                        }
                        for ( int i = 1 ; i < barSpots.length ; i++ ) {
                            if ( barSpots[i] > maxChoose+barSpots[i-1]+1 ) {
                                return false;
                            }
                        }
                        return true;
                    }
                    private void advance() {
                        int biggestThatCanMove = barSpots.length-2;
                        while ( biggestThatCanMove >= 0
                            && ( barSpots[biggestThatCanMove]+1 >= barSpots[biggestThatCanMove+1] ) ) {
                            biggestThatCanMove--;
                        }
                        fillIncreasing(barSpots,biggestThatCanMove,
                                   barSpots[biggestThatCanMove]+1,
                                   barSpots.length-1);
                    }
                    public boolean hasNext() {
                        return barSpots[0] == 0;
                    }
                    public List<T> next() {
                        List<T> toRet = new ArrayList<T>();
                        for ( int i = 0 ; i+1 < barSpots.length ; i++ ) {
                            int times = barSpots[i+1]-barSpots[i]-1;
                            for ( boolean ignore : new boolean[times] ) {
                                toRet.add(set[i]);
                            }
                        }
                        do {
                            advance();
                        } while ( hasNext() && !readyToReturn() );
                        return toRet;
                    }
                    public void remove() {
                        throw new UnsupportedOperationException();
                    }
                };
            }
        };
    }
}
于 2013-08-16T23:01:52.953 に答える