这是一个创建于 709 天前的主题，其中的信息可能已经有所发展或是发生改变。
有一组三维坐标数据 [{x, y, z}, {x, y, z}, ...], 现在需要随机生成一个坐标 且不能和已有坐标重复
x y z 最大值 = 100
请教有什么算法可以实现这个需求吗?
 |
1
momocraft 2022-12-23 17:17:14 +08:00
如果坐标是整数: 把原来的坐标整成带排序的数据结构，然后在“空洞”里随机生成就不会重复
|
 |
2
ianEros 2022-12-23 17:26:19 +08:00
我想到的也是提前把未使用的坐标存起来，然后在这个集合里面随机，如果最大值 100 ，size 最大值也就 1 ，000 ，000
|
 |
3
zxCoder 2022-12-23 17:27:00 +08:00
随机就是一种算法，随机算法
|
 |
4
shyrock 2022-12-23 17:36:57 +08:00
感觉跟 hash 的思路有点像。
OP 能说一下问题的真实背景吗？ |
 |
5
xuanzizhe 2022-12-23 18:16:35 +08:00
想到的最原始的方法就是先把坐标算出来存在数组里，然后取的时候每次从里面删一条，没啥算法可言了，相信应该有更好的方法勒~ https://reurl.cc/gQpdNX
|
 |
6
vace 2022-12-23 18:24:38 +08:00  1
整数的话 xyz 直接转固定长度二进制就行了
0b1100100 0b1100100 0b1100100 => 0b110010011001001100100 也就：0 ～ 1651300 ，随机生成点数字的工作。 |
 |
7
xuanbg 2022-12-23 18:26:10 +08:00
建立一个 size 为 100 的 3 维空间，就是一个[100,100,100]的 3 维数组并初始化好。然后随机在这个 3 维空间中取一个就行空的点就行了。
|
 |
8
Tanix2 2022-12-23 18:28:01 +08:00 via iPhone
从已有坐标构建哈希表，随机生成坐标，通过比较哈西判断是否重复，重复则重新随机生成。
|
 |
9
shiji 2022-12-23 18:30:55 +08:00 via iPhone
评论区真是精彩啊。 不看不知道，一看吓一跳。
|
 |
10
Jakarta 2022-12-23 19:34:42 +08:00 via Android
原始坐标数据转成"到原点距离: [坐标,坐标,....]"的哈希，随机生成的坐标也计算一下到原点的距离，如果距离存在，就进一步比较坐标值。
不知是否可行？ |
 |
11
wxf666 2022-12-23 19:55:34 +08:00
如果取值范围是 0 ~ 100 ，一个三维坐标可以映射到一个 0 ~ (101^3-1) 的整数，后面就是生成不重复的随机整数就好
如果换成 bitmap 存储，大概只需 16 KB 内存即可？ |
 |
12
9ine 2022-12-23 20:17:35 +08:00
|
 |
15
pagxir 2022-12-24 23:19:10 +08:00 via Android
看描述，可选集合是个有限集合。却没有说有限次数，那大概率是无解。如果只是想把数据顺序乱掉，那就直接用洗牌算法将数据打乱就可以了。
|
|
16
pagxir 2022-12-24 23:31:33 +08:00 via Android
得到打乱数据，也可以采取抽卡牌的方式，就是从中随机抽中一张，然后跟最顶部一张交换，接着扔掉最顶部的一张，持续这么下去，就得到打乱的数据了。
|
 |
17
sillydaddy 2022-12-25 11:14:13 +08:00
算法：
``` type Point={x:number, y:number, z:number}; let blacklist:Point[] = [....................]; //初始化已有的三维坐标数据 let pickRandomPointThatIsNotInBlackList = ():Point=>{ while(true){ let x=Math.random()*100; let y=Math.random()*100; let z=Math.random()*100; let inBlackList = blacklist.every(v=>!(v.x==x&&v.y==y&&v.z==z)); if(!inBlackList) return {x,y,z}; } } ``` 测试： console.log( pickRandomPointThatIsNotInBlackList() ); |
|
18
sillydaddy 2022-12-25 11:16:13 +08:00
```
let inBlackList = blacklist.every(v=>!(v.x==x&&v.y==y&&v.z==z)); if(!inBlackList) return {x,y,z}; } ``` 改为 ``` let notInBlackList = blacklist.every(v=>!(v.x==x&&v.y==y&&v.z==z)); if(notInBlackList) return {x,y,z}; } ``` |
|
19
sillydaddy 2022-12-25 11:20:32 +08:00
所以算法就是：先随机出一个坐标点，然后判断一下是否在已有的三维坐标数组中，如果在，就再随机出一个坐标点。直到得到符合条件的点。得到不同坐标点的概率是相等的。
|
 |
20
Rootrl 2022-12-28 16:41:09 +08:00
用 Hashmap 维护已有坐标，用一个连接符把 xyz 字符拼起来做 key ，比如"x-y-z"，value 随便设置个单字符。剩下就是生成了，然后一样拼起来拿去 hashmap 检索判断
|
Select Language