0

我想枚举长度为 N 的所有向量，其中每个元素的值可以为 [0 ... K] 并且所有元素的总和为 SUM。

我使用递归函数解决了这个问题，但是当我在 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 3011 3002 2300 2210 2201 2120111 2111 211120202020202021 2012 2003 2003 1310 1310 1301 1220 1211 1211 12102 1130 1121 1121 1112 1112 1103 1031 1022 1013 1013 1013 0320 0320 0320 0311 0310 2310230 02330 0221 0221 0221 02212120212 020301301301312222222222222222222222222222222222222222222222222222222222222222222222222222222222222222转

0023

4

2 回答 2

2

__device__CUDA 支持具有计算能力 (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酒吧。条形将星星分隔成 bin，i第 th 个 bin 中的星星数是条目的大小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 回答