1

我已经开始构建这样的东西：

class Node{
    Node next,prev;
    int val;
    Node(int val, Node prev, Node next){
        this.val = val;
        this.prev = prev;
        this.next = next;
    }
}

……

 public void buildRandomPath(int size, int total){
    road = new Node[size];
    int tmp = (int)(Math.random()*(double)(total/size));
    total = total-tmp;
    road[0] = new Node(tmp,road[size-1],road[1]);
    for (int i = 1; i < size-1; i++){
        tmp = (int)(Math.random()*(double)(total/size-i));
        total = total-tmp;
        road[i] = new Node(tmp1,road[i-1],road[i+1]);
    }
    tmp = (int)(Math.random()*(double)(total));
    total = total-tmp;
    road[size-1] = new Node(tmp,road[size-2],road[0]);
}

这完全不是正确的算法，但这是我的总体思路

4

6 回答 6

2

对于统一的随机答案（假设隐含非负约束）：在包含和排除nodeCount - 1之间生成成对不同的整数。对这些、 prepend和 append进行排序。返回差序列减一。0sum + nodeCount - 1-1sum + nodeCount - 1

示例：nodeCount = 4和sum = 10。生成整数。

5 2 12

排序，前置，附加。

-1 2 5 12 13

差序。

3 3 7 1

减一。

2 2 6 0

实施说明：如果有可能，您需要特殊情况nodeCount == 0。要生成没有重复的整数：如果sum与 相比较小nodeCount，则使用部分 Fisher--Yates shuffle。否则，nodeCount - 1使用替换抽样整数并重复，直到没有重复。

于 2013-04-27T14:38:37.417 回答
0 
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;


class Node{
    Node next,prev;
    int val;
}

public class temp {

    public Node[] buildRandomPath(int size, int total){

        Node[] road = new Node[size];
        for (int i = 0; i < road.length; i++) {
            road[i]=new Node();
        } 

         int tmp = (int)(Math.random()*(double)(total/size));
        if(tmp==0)
            tmp=1;
        total = total-tmp;
        road[0].val=tmp;
        road[0].next=road[1];
        road[0].prev=road[size-1];  
        int tmp1=0;
        for (int i = 1; i < size-1; i++){
            tmp1 = (int)(Math.random()*(double)(total/size-i));
            if(tmp1==0)
                tmp1=1;
            total = total-tmp1;
            road[i].next=road[i+1];
            road[i].prev=road[i-1];
            if(total>0)
                road[i].val=tmp1;
            else
                road[i].val=0;
        }
        road[size-1].val=total;
        road[size-1].next=road[0];
        road[size-1].prev=road[size-2];
        return road;
    }
    public static void main(String[] args) {

        temp t=new temp();
        Node[] node=t.buildRandomPath(10, 500);
        int i=0;
        for (Node node2 : node) {
            i=i+node2.val;

    }
        System.out.println(i);
    }
}
于 2013-07-10T12:44:31.540 回答
0

你可以这样做：

double runningTotal = total;
Random rand = new Random();
road = new double[size];
while(runningTotal > 0) {
    double temp = rand.nextDouble(); // return [0, 1)
    if(temp > runningTotal) {
        temp = runningTotal;
        runningTotal = 0.0;
    } else {
        runningTotal -= temp;
    }
    road[rand.nextInt(size)] += temp;
}

您可以替换temp = rand.nextDouble()为temp = rand.nextDouble / scalingFactor（例如 scalingFactor = 10）以增加均匀性并降低任何节点最终等于 0 的概率。

于 2013-04-27T15:37:02.133 回答
0

如果您希望总和成为特定的总数，您可以有一个剩余的总数并将最后一个元素设为该值。例如

使节点具有随机值 X1, X2, ... Xn-1, total - SumOf(X1, ... Xn-1) 这将确保总数始终为total

于 2013-04-27T14:21:53.533 回答
0 
public Node[] buildRandomPath(int size, int total){
    Node[] road = new Node[size];
    int tmp = (int)(Math.random()*(double)(total/size));
    if(tmp==0)
        tmp=1;
    total = total-tmp;
    road[0] = new Node(tmp,road[size-1],road[1]);
    int tmp1=0;
    for (int i = 1; i < size-1; i++){
        tmp1 = (int)(Math.random()*(double)(total/size-i));
        if(tmp1==0)
            tmp1=1;
        total = total-tmp1;
        if(total>0)
            road[i] = new Node(tmp1,road[i-1],road[i+1]);
        else
            road[i] = new Node(0,road[i-1],road[i+1]);
    }
    road[size-1] = new Node(total,road[size-2],road[0]);
    return road;
}
于 2013-07-09T13:23:52.087 回答
0

如果要生成 n 个值，总和为 S，则可以生成 n 个介于 0 和 1 之间的随机双精度数，然后将它们除以使它们的总和为 1。然后将值乘以 S。如果数字必须是整数，可能需要一些额外的工作来正确处理舍入。

于 2013-04-27T14:27:18.910 回答