목록의 제한된 무작위 순열을 많이 만듭니다.
https://stackoverflow.com/questions/93353
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
무작위 순열 목록을 만들어야 합니다.요소는 무엇이든 될 수 있지만 정수 0부터 x-1까지라고 가정합니다.나는 각각 z 요소를 포함하는 y 목록을 만들고 싶습니다.규칙은 어떤 목록에도 동일한 요소가 두 번 포함될 수 없으며 모든 목록에서 각 요소가 사용되는 횟수는 동일하거나 최대한 가깝다는 것입니다.예를 들어, 내 요소가 0,1,2,3이고 y가 6이고 z가 2인 경우 가능한 해결책은 다음과 같습니다.
0,3 1,2 3,0 2,1 0,1 2,3
각 행에는 고유한 요소만 있으며 요소는 3회 이상 사용되지 않았습니다.y가 7이면 요소 2개가 4번 사용되고 나머지는 3번 사용됩니다.
해결책
이는 개선될 수 있지만 해당 작업을 수행하는 것 같습니다(Python).
import math, random
def get_pool(items, y, z):
slots = y*z
use_each_times = slots/len(items)
exceptions = slots - use_each_times*len(items)
if (use_each_times > y or
exceptions > 0 and use_each_times+1 > y):
raise Exception("Impossible.")
pool = {}
for n in items:
pool[n] = use_each_times
for n in random.sample(items, exceptions):
pool[n] += 1
return pool
def rebalance(ret, pool, z):
max_item = None
max_times = None
for item, times in pool.items():
if times > max_times:
max_item = item
max_times = times
next, times = max_item, max_times
candidates = []
for i in range(len(ret)):
item = ret[i]
if next not in item:
candidates.append( (item, i) )
swap, swap_index = random.choice(candidates)
swapi = []
for i in range(len(swap)):
if swap[i] not in pool:
swapi.append( (swap[i], i) )
which, i = random.choice(swapi)
pool[next] -= 1
pool[swap[i]] = 1
swap[i] = next
ret[swap_index] = swap
def plist(items, y, z):
pool = get_pool(items, y, z)
ret = []
while len(pool.keys()) > 0:
while len(pool.keys()) < z:
rebalance(ret, pool, z)
selections = random.sample(pool.keys(), z)
for i in selections:
pool[i] -= 1
if pool[i] == 0:
del pool[i]
ret.append( selections )
return ret
print plist([0,1,2,3], 6, 2)
다른 팁
좋습니다. 이를 근사화하는 한 가지 방법은 다음과 같습니다.
1 - 목록을 섞으세요
2 - y개의 첫 번째 요소를 가져와 다음 행을 형성합니다.
4 - 목록에 숫자가 있는 한 (2)를 반복합니다.
5 - 목록을 완성할 만큼 숫자가 충분하지 않은 경우 원래 목록을 다시 섞고 누락된 요소를 가져오며 숫자를 다시 가져오지 않도록 하세요.
6 - 행이 필요한 한 단계 (2)부터 다시 시작하세요.
나는 이것이 당신이 할 수 있는 만큼 무작위여야 하며 확실히 당신의 기준을 따를 것이라고 생각합니다.게다가 중복 요소에 대한 테스트도 거의 없습니다.
첫째, 목록의 마지막에는 항상 무작위로 정렬할 수 있으므로 "무작위 순열"(어려움)을 만드는 것에 대해 걱정하지 마세요.1) 순열 만들기(쉬움)와 2) 무작위 추출(쉬움)만 걱정하면 됩니다.
"진정한" 무작위 그룹을 원한다면 본질적으로 무작위화가 결과의 "균등한 분포"라는 제약을 실제로 허용하지 않는다는 점을 받아들여야 합니다. 이를 얻을 수도 있고 비슷한 모양의 그룹을 얻을 수도 있습니다.정말 균일하게 배포하려면 먼저 세트를 균등하게 배포한 다음 무작위로 그룹화하세요.
세트 x의 각 요소를 균등하게 사용해야 합니까?다음과 같은 해석을 할 수 없다는 것이 규칙에서 명확하지 않습니다.
다음 사항에 유의하세요."모든 목록에서 각 요소가 사용되는 횟수는 동일합니다(또는 최대한 가깝습니다)."
이 기준과 z < x* 규칙을 기반으로 모든 목록의 모든 항목을 간단하게 열거할 수 있다고 가정합니다.따라서 자동으로 z 위치에 열거된 항목의 y 목록을 만듭니다.귀하의 예는 내 버전만큼 위의 규칙을 충족하지 않습니다.x={0,1,2,3} y=6 및 z=2의 예를 사용하면 다음을 얻습니다.0,1 0,1 0,1 0,1 0,1 0,1
이제는 2~3개도 안 썼는데, 다 써야 한다고는 안 하셨어요.그것들을 모두 사용해야 하고 사용법에 "가능한 한 가깝다"는 것을 증명할 수 없다면 목록을 통해 모든 항목을 다음과 같이 열거하면 됩니다.0,1 2,3 0,1 2,3 0,1 2,3
마지막으로, 실제로 모든 요소를 사용해야 한다고 가정해 보겠습니다.각 요소가 몇 번 반복될 수 있는지 계산하려면 (y*z)/(x 개수)만 사용하면 됩니다.그렇게 하면 목록의 항목을 어떻게 나눌 것인지 앉아서 고민할 필요가 없습니다.나머지가 있거나 결과가 1보다 작으면 정확한 반복 횟수를 얻을 수 없다는 것을 알고 있으므로 이러한 경우 완벽하게 만들기 위해 계산 에너지를 낭비하는 것은 별로 중요하지 않습니다.나는 여전히 위와 같이 열거하고 여기에서 계산을 사용하여 완벽한 결과가 달성되었거나 달성되지 않은 이유를 보여주는 것이 가장 빠른 결과라고 주장합니다.이 계산에서 중복된 위치 수를 추출하는 멋진 알고리즘을 얻을 수 있지만 "여백에 맞추기에는 너무 깁니다."
*각 목록에는 동일한 z개의 요소가 있으므로 z가 x보다 큰 목록을 만드는 것은 불가능하며 목록에 동일한 요소가 두 번 포함될 수 없다는 규칙은 여전히 충족됩니다.따라서 이 규칙은 z가 x보다 클 수 없음을 요구합니다.
의견의 새로운 세부 사항을 기반으로 솔루션은 단순히 표준 무작위 순열 생성 알고리즘을 구현하는 것일 수 있습니다.여기에는 무작위 순열 생성 알고리즘에 대한 긴 논의가 있습니다.
http://www.techuser.net/randpermgen.html
(구글 검색에서:무작위 순열 생성)
이것은 Ruby에서 작동합니다.
# list is the elements to be permuted
# y is the number of results desired
# z is the number of elements per result
# equalizer keeps track of who got used how many times
def constrained_permutations list, y, z
list.uniq! # Never trust the user. We want no repetitions.
equalizer = {}
list.each { |element| equalizer[element] = 0 }
results = []
# Do this until we get as many results as desired
while results.size < y
pool = []
puts pool
least_used = equalizer.each_value.min
# Find how used the least used element was
while pool.size < z
# Do this until we have enough elements in this resultset
element = nil
while element.nil?
# If we run out of "least used elements", then we need to increment
# our definition of "least used" by 1 and keep going.
element = list.shuffle.find do |x|
!pool.include?(x) && equalizer[x] == least_used
end
least_used += 1 if element.nil?
end
equalizer[element] += 1
# This element has now been used one more time.
pool << element
end
results << pool
end
return results
end
샘플 사용법:
constrained_permutations [0,1,2,3,4,5,6], 6, 2
=> [[4, 0], [1, 3], [2, 5], [6, 0], [2, 5], [3, 6]]
constrained_permutations [0,1,2,3,4,5,6], 6, 2
=> [[4, 5], [6, 3], [0, 2], [1, 6], [5, 4], [3, 0]]
enter code here
