java - 如何建立一个链表，每个节点都会有一个随机的int值，但是总值sum和节点数会预先固定？

Question

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

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]);
}

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

Answer 1

对于统一的随机答案(假设隐式非负性约束):生成 nodeCount - 1 两两不同的整数，介于 0 和 sum + nodeCount - 之间1 独家。对这些进行排序，在 -1 前面加上 sum + 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 洗牌。否则，对 nodeCount - 1 整数进行替换并重复采样，直到没有重复项为止。