인접한 동일한 요소없이 목록의 모든 순열 생성
목록을 정렬 할 때
a = [1,2,3,3,2,2,1]
sorted(a) => [1, 1, 2, 2, 2, 3, 3]
결과 목록에서 동일한 요소는 항상 인접 해 있습니다.
반대 작업을 어떻게 수행 할 수 있습니까? 동일한 요소가 인접하지 않도록 (또는 가능한 한 드물게) 목록을 섞으십시오.
예를 들어, 위 목록에서 가능한 솔루션 중 하나는 다음과 같습니다.
p = [1,3,2,3,2,1,2]
보다 공식적으로 주어진 list 는 쌍의 수를 최소화 a하는 순열 p을 생성합니다 p[i]==p[i+1].
목록이 크기 때문에 모든 순열을 생성하고 필터링하는 것은 옵션이 아닙니다.
보너스 질문 : 이러한 모든 순열을 효율적으로 생성하는 방법은 무엇입니까?
다음은 솔루션을 테스트하는 데 사용하는 코드입니다. https://gist.github.com/gebrkn/9f550094b3d24a35aebd
UPD : 많은 사람들이 훌륭한 답변을 게시했기 때문에 여기서 우승자를 선택하는 것은 어려운 선택이었습니다. @VincentvanderWeele , @David Eisenstat , @Coady , @ enrico.bacis 및 @srgerg 는 최상의 순열을 완벽하게 생성하는 함수를 제공했습니다. @tobias_k 와 David도 보너스 질문에 답했습니다 (모든 순열 생성). 정확성 증명을 위해 David에게 추가 포인트.
@VincentvanderWeele의 코드가 가장 빠른 것으로 보입니다.
이것은 Thijser의 현재 불완전한 의사 코드 라인을 따른 것입니다. 아이디어는 방금 가져온 것이 아니라면 나머지 항목 유형 중 가장 자주 사용하는 것입니다. ( 이 알고리즘 의 Coady 구현 도 참조하십시오 .)
import collections
import heapq
class Sentinel:
pass
def david_eisenstat(lst):
counts = collections.Counter(lst)
heap = [(-count, key) for key, count in counts.items()]
heapq.heapify(heap)
output = []
last = Sentinel()
while heap:
minuscount1, key1 = heapq.heappop(heap)
if key1 != last or not heap:
last = key1
minuscount1 += 1
else:
minuscount2, key2 = heapq.heappop(heap)
last = key2
minuscount2 += 1
if minuscount2 != 0:
heapq.heappush(heap, (minuscount2, key2))
output.append(last)
if minuscount1 != 0:
heapq.heappush(heap, (minuscount1, key1))
return output
정확성 증명
개수가 k1 및 k2 인 두 항목 유형의 경우 최적 솔루션은 k1 <k2 인 경우 k2-k1-1 개의 결함, k1 = k2 인 경우 0 개의 결함, k1> k2 인 경우 k1-k2-1 개의 결함을 갖습니다. = 경우는 분명합니다. 나머지는 대칭입니다. 소수 요소의 각 인스턴스는 가능한 총 k1 + k2-1 중 최대 2 개의 결함을 방지합니다.
이 탐욕스러운 알고리즘은 다음 논리에 따라 최적의 솔루션을 반환합니다. 최적의 솔루션으로 확장되는 경우 접두사 (부분 솔루션)를 안전하다고 부릅니다 . 분명히 빈 접두사는 안전하며 안전한 접두사가 전체 솔루션이면 해당 솔루션이 최적입니다. 탐욕스러운 각 단계가 안전을 유지한다는 것을 귀납적으로 보여주는 것으로 충분합니다.
탐욕스러운 단계가 결함을 유발하는 유일한 방법은 항목 유형이 하나만 남아있는 경우 계속할 수있는 방법이 하나 뿐이며 그 방법이 안전합니다. 그렇지 않으면 고려중인 단계 바로 전에 P를 (안전한) 접두사로, P '를 바로 뒤의 접두사로, S를 P를 확장하는 최적의 솔루션으로 둡니다. S도 P'를 확장하면 완료됩니다. 그렇지 않으면 P '= Px 및 S = PQ 및 Q = yQ'로 설정합니다. 여기서 x와 y는 항목이고 Q와 Q '는 시퀀스입니다.
먼저 P가 y로 끝나지 않는다고 가정합니다. 알고리즘의 선택에 따라 x는 적어도 Q에서 y만큼 자주 발생합니다. x와 y 만 포함하는 Q의 최대 부분 문자열을 고려하십시오. 첫 번째 부분 문자열에 최소한 y만큼 x가있는 경우 x로 시작하는 추가 결함없이 다시 작성할 수 있습니다. 첫 번째 부분 문자열이 x보다 더 많은 y를 가지고 있다면, 다른 부분 문자열은 y보다 더 많은 x를 가지고 있으며, x가 먼저 나오도록 추가 결함없이이 부분 문자열을 다시 쓸 수 있습니다. 두 경우 모두 필요에 따라 P '를 확장하는 최적 솔루션 T를 찾습니다.
이제 P가 y로 끝난다고 가정합니다. x의 첫 번째 발생을 앞으로 이동하여 Q를 수정합니다. 그렇게함으로써 우리는 최대 하나의 결함 (x가 있었던 곳)을 도입하고 하나의 결함 (yy)을 제거합니다.
모든 솔루션 생성
이것은 tobias_k의 답변 과 현재 고려중인 선택이 어떤 식 으로든 전역 적으로 제한되는 경우를 감지하는 효율적인 테스트입니다. 생성 오버 헤드가 출력 길이의 순서이기 때문에 점근 적 실행 시간이 최적입니다. 불행히도 최악의 경우 지연은 2 차입니다. 더 나은 데이터 구조로 선형 (최적)으로 축소 될 수 있습니다.
from collections import Counter
from itertools import permutations
from operator import itemgetter
from random import randrange
def get_mode(count):
return max(count.items(), key=itemgetter(1))[0]
def enum2(prefix, x, count, total, mode):
prefix.append(x)
count_x = count[x]
if count_x == 1:
del count[x]
else:
count[x] = count_x - 1
yield from enum1(prefix, count, total - 1, mode)
count[x] = count_x
del prefix[-1]
def enum1(prefix, count, total, mode):
if total == 0:
yield tuple(prefix)
return
if count[mode] * 2 - 1 >= total and [mode] != prefix[-1:]:
yield from enum2(prefix, mode, count, total, mode)
else:
defect_okay = not prefix or count[prefix[-1]] * 2 > total
mode = get_mode(count)
for x in list(count.keys()):
if defect_okay or [x] != prefix[-1:]:
yield from enum2(prefix, x, count, total, mode)
def enum(seq):
count = Counter(seq)
if count:
yield from enum1([], count, sum(count.values()), get_mode(count))
else:
yield ()
def defects(lst):
return sum(lst[i - 1] == lst[i] for i in range(1, len(lst)))
def test(lst):
perms = set(permutations(lst))
opt = min(map(defects, perms))
slow = {perm for perm in perms if defects(perm) == opt}
fast = set(enum(lst))
print(lst, fast, slow)
assert slow == fast
for r in range(10000):
test([randrange(3) for i in range(randrange(6))])
의사 코드 :
- 목록 정렬
- 정렬 된 목록의 전반부를 반복하고 결과 목록의 모든 짝수 인덱스를 채 웁니다.
- 정렬 된 목록의 후반부를 반복하고 결과 목록의 모든 홀수 인덱스를 채 웁니다.
p[i]==p[i+1]입력의 절반 이상이 동일한 요소로 구성되는 경우 에만 가능 하며,이 경우 동일한 요소를 연속 스팟에 넣는 것 외에 다른 선택이 없습니다 (피전 홀 원칙에 따라).
주석에서 지적했듯이,이 접근 방식은 요소 중 하나가 적어도 n/2몇 번 발생하는 경우 (또는 n/2+1홀수 일 경우, 짝수 및 홀수 모두 n에 (n+1)/2)대해 일반화 되는 경우) 하나의 충돌이 너무 많이 발생할 수 있습니다 . 이러한 요소는 최대 두 개이며 두 개가 있으면 알고리즘이 제대로 작동합니다. 유일한 문제는 적어도 절반의 시간 동안 발생하는 요소가 하나 일 때입니다. 우리는 요소를 찾고 먼저 처리함으로써 간단히이 문제를 해결할 수 있습니다.
나는 이것을 제대로 작성하기 위해 파이썬에 대해 충분히 알지 못하기 때문에 github에서 이전 버전의 OP 구현을 복사 할 자유를 얻었습니다.
# Sort the list
a = sorted(lst)
# Put the element occurring more than half of the times in front (if needed)
n = len(a)
m = (n + 1) // 2
for i in range(n - m + 1):
if a[i] == a[i + m - 1]:
a = a[i:] + a[:i]
break
result = [None] * n
# Loop over the first half of the sorted list and fill all even indices of the result list
for i, elt in enumerate(a[:m]):
result[2*i] = elt
# Loop over the second half of the sorted list and fill all odd indices of the result list
for i, elt in enumerate(a[m:]):
result[2*i+1] = elt
return result
이전 항목이 아닌 가장 일반적인 항목을 남겨 두는 이미 주어진 알고리즘은 정확합니다. 다음은 가장 일반적인 것을 추적하기 위해 힙을 최적으로 사용하는 간단한 구현입니다.
import collections, heapq
def nonadjacent(keys):
heap = [(-count, key) for key, count in collections.Counter(a).items()]
heapq.heapify(heap)
count, key = 0, None
while heap:
count, key = heapq.heapreplace(heap, (count, key)) if count else heapq.heappop(heap)
yield key
count += 1
for index in xrange(-count):
yield key
>>> a = [1,2,3,3,2,2,1]
>>> list(nonadjacent(a))
[2, 1, 2, 3, 1, 2, 3]
재귀 적 역 추적 알고리즘을 사용하여 '완벽하게 정렬되지 않은'순열 (인접한 위치에 두 개의 동일한 요소가 없음)을 모두 생성 할 수 있습니다 . 실제로 모든 순열을 생성하는 유일한 차이점은 마지막 숫자를 추적하고 그에 따라 일부 솔루션을 제외한다는 것입니다.
def unsort(lst, last=None):
if lst:
for i, e in enumerate(lst):
if e != last:
for perm in unsort(lst[:i] + lst[i+1:], e):
yield [e] + perm
else:
yield []
이 형식의 함수는 많은 하위 목록을 생성하므로 그다지 효율적이지 않습니다. 또한 가장 제한적인 숫자 (가장 많은 숫자)를 먼저 살펴봄으로써 속도를 높일 수 있습니다. counts숫자 만 사용하는 훨씬 더 효율적인 버전 이 있습니다.
def unsort_generator(lst, sort=False):
counts = collections.Counter(lst)
def unsort_inner(remaining, last=None):
if remaining > 0:
# most-constrained first, or sorted for pretty-printing?
items = sorted(counts.items()) if sort else counts.most_common()
for n, c in items:
if n != last and c > 0:
counts[n] -= 1 # update counts
for perm in unsort_inner(remaining - 1, n):
yield [n] + perm
counts[n] += 1 # revert counts
else:
yield []
return unsort_inner(len(lst))
이를 사용하여 next완벽한 순열 을 생성 하거나 list모두 보유 할 수 있습니다. 그러나 완벽하게 정렬되지 않은 순열 이 없는 경우이 생성기는 결과적으로 결과를 생성 하지 않습니다 .
>>> lst = [1,2,3,3,2,2,1]
>>> next(unsort_generator(lst))
[2, 1, 2, 3, 1, 2, 3]
>>> list(unsort_generator(lst, sort=True))
[[1, 2, 1, 2, 3, 2, 3],
... 36 more ...
[3, 2, 3, 2, 1, 2, 1]]
>>> next(unsort_generator([1,1,1]))
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration
이 문제를 피하기 위해 다른 답변에서 제안 된 알고리즘 중 하나와 함께이를 대체로 사용할 수 있습니다. 이렇게하면 완벽하게 정렬되지 않은 순열이 있으면 반환하고 그렇지 않으면 좋은 근사값을 반환합니다.
def unsort_safe(lst):
try:
return next(unsort_generator(lst))
except StopIteration:
return unsort_fallback(lst)
파이썬에서는 다음을 수행 할 수 있습니다.
정렬 된 목록이 있다고 생각하면 l다음을 수행 할 수 있습니다.
length = len(l)
odd_ind = length%2
odd_half = (length - odd_ind)/2
for i in range(odd_half)[::2]:
my_list[i], my_list[odd_half+odd_ind+i] = my_list[odd_half+odd_ind+i], my_list[i]
이는 제자리에있는 작업이므로 다소 빠릅니다 ( O(N)). 에서 l[i] == l[i+1]로 이동 l[i] == l[i+2]하므로 결국 순서는 무작위가 아니지만 내가 질문을 이해하는 방식에서 찾고있는 무작위성이 아닙니다.
아이디어는 정렬 된 목록을 중간에 분할 한 다음 두 부분의 다른 모든 요소를 교환하는 것입니다.
이를 l= [1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]위해l = [3, 1, 4, 2, 5, 1, 3, 1, 4, 2, 5]
이 메서드 l[i] == l[i + 1]는 한 요소의 풍부도가 목록 길이의 절반보다 크거나 같으면 모든 요소를 제거하지 못합니다 .
위의 내용은 가장 빈번한 요소가 목록 크기의 절반보다 작은 한 잘 작동하지만 다음 함수는 다른 모든 요소가 다음으로 시작 하는 제한 사례 (유명한 개별 문제) 도 처리합니다 . 첫 번째는 가장 풍부한 것이어야합니다.
def no_adjacent(my_list):
my_list.sort()
length = len(my_list)
odd_ind = length%2
odd_half = (length - odd_ind)/2
for i in range(odd_half)[::2]:
my_list[i], my_list[odd_half+odd_ind+i] = my_list[odd_half+odd_ind+i], my_list[i]
#this is just for the limit case where the abundance of the most frequent is half of the list length
if max([my_list.count(val) for val in set(my_list)]) + 1 - odd_ind > odd_half:
max_val = my_list[0]
max_count = my_list.count(max_val)
for val in set(my_list):
if my_list.count(val) > max_count:
max_val = val
max_count = my_list.count(max_val)
while max_val in my_list:
my_list.remove(max_val)
out = [max_val]
max_count -= 1
for val in my_list:
out.append(val)
if max_count:
out.append(max_val)
max_count -= 1
if max_count:
print 'this is not working'
return my_list
#raise Exception('not possible')
return out
else:
return my_list
다음은 좋은 알고리즘입니다.
우선 얼마나 자주 발생하는지 모든 숫자를 계산합니다. 지도에 답을 넣으십시오.
가장 자주 발생하는 숫자가 먼저 오도록이지도를 정렬합니다.
답변의 첫 번째 숫자는 정렬 된지도의 첫 번째 숫자입니다.
첫 번째가 이제 하나 더 작아 지도록지도를 선택합니다.
효율성을 높이려면 정렬 단계의 효율성을 높이는 방법을 찾으십시오.
보너스 질문에 대한 대답 : 이것은 인접한 요소가 동일 할 수없는 집합의 모든 순열을 찾는 알고리즘입니다. 나는 이것이 개념적으로 가장 효율적인 알고리즘이라고 믿습니다 (다른 사람들은 더 간단한 코드로 번역되기 때문에 실제로 더 빠를 수 있습니다). 무차별 대입을 사용하지 않고 고유 한 순열 만 생성하며 솔루션으로 연결되지 않는 경로는 가장 빠른 시점에서 차단됩니다.
다른 모든 요소를 합친 것보다 더 자주 발생하는 집합의 요소에는 "풍부한 요소"라는 용어를 사용하고, 다른 요소의 수를 뺀 풍부한 요소의 수에는 "풍부한 요소"라는 용어를 사용합니다.
예를 들어, 세트는 abac더 풍부한 요소 세트가없는 abaca그리고 aabcaa이 a풍부한 원소로서 및 풍부도 1 및도 2에 각각.
- 다음과 같은 세트로 시작하십시오.
aaabbcd
- 반복에서 첫 번째 발생을 분리하십시오.
첫 번째 : abcd
반복 : aab
- 반복에서 풍부한 요소 (있는 경우)를 찾고 풍부도를 계산합니다.
풍부한 요소 :
풍부 : 1
- 풍부한 요소 뒤의 요소 수가 풍부도보다 적지 않은 첫 번째 순열을 모두 생성합니다. 예에서 "a"는 마지막이 될 수 없습니다.
abcd, abdc, acbd, acdb, adbc, adcb, bacd, badc, bcad,
bcda, bdac,bdca,
cabd, cadb, cbad,cbda, cdab,cdba, dabc, dacb, abac,dbca, dcab,dcba
- 각 순열에 대해 다음 규칙에 따라 반복되는 문자 집합을 하나씩 삽입합니다.
5.1. 집합의 풍부도가 지금까지 순열에서 풍부한 요소가 마지막으로 발생한 이후의 요소 수보다 크면 다음 순열로 건너 뜁니다.
예를 들어 지금까지 순열이abc이면 풍부한 요소a가 있는 집합 은 풍부도가 2 이하인 경우에만 삽입 할 수 있으므로aaaabc괜찮습니다aaaaabc.5.2. 순열의 마지막 항목이 먼저 오는 집합에서 요소를 선택합니다.
예를 들어, 순열 지금까지 때abcba와 세트 인ab선택b5.3. 선택한 요소를 순열의 마지막 항목 오른쪽에 최소 2 개 위치에 삽입합니다.
예를 들어b순열에 삽입 할 때babca결과는 다음babcba과 같습니다.babcab5.4. 각 결과 순열과 나머지 세트로 5 단계를 반복합니다.
EXAMPLE:
set = abcaba
firsts = abc
repeats = aab
perm3 set select perm4 set select perm5 set select perm6
abc aab a abac ab b ababc a a ababac
ababca
abacb a a abacab
abacba
abca ab b abcba a -
abcab a a abcaba
acb aab a acab ab a acaba b b acabab
acba ab b acbab a a acbaba
bac aab b babc aa a babac a a babaca
babca a -
bacb aa a bacab a a bacaba
bacba a -
bca aab -
cab aab a caba ab b cabab a a cababa
cba aab -
이 알고리즘은 고유 한 순열을 생성합니다. 순열의 총 수 ( abaa를 전환 할 수 있기 때문에 두 번 계산 됨) 를 알고 싶다면 고유 한 순열 수에 인수를 곱합니다.
F = N 1 ! * N 2 ! * ... * N n !
여기서 N은 집합에있는 각 요소의 발생 횟수입니다. 세트의 경우 abcdabcaba이것은 4입니다! * 삼! * 2! * 1! 또는 288은 고유 한 순열 만이 아닌 모든 순열을 생성하는 알고리즘이 얼마나 비효율적인지 보여줍니다. 이 경우 모든 순열을 나열하려면 고유 순열을 288 번 나열하세요. :-)
아래는 자바 스크립트의 (다소 서투른) 구현입니다. 나는 파이썬과 같은 언어가 이런 종류의 것에 더 적합 할 것이라고 생각합니다. 코드 조각을 실행하여 "abracadabra"의 분리 된 순열을 계산합니다.
// FIND ALL PERMUTATONS OF A SET WHERE NO ADJACENT ELEMENTS ARE IDENTICAL
function seperatedPermutations(set) {
var unique = 0, factor = 1, firsts = [], repeats = [], abund;
seperateRepeats(set);
abund = abundance(repeats);
permutateFirsts([], firsts);
alert("Permutations of [" + set + "]\ntotal: " + (unique * factor) + ", unique: " + unique);
// SEPERATE REPEATED CHARACTERS AND CALCULATE TOTAL/UNIQUE RATIO
function seperateRepeats(set) {
for (var i = 0; i < set.length; i++) {
var first, elem = set[i];
if (firsts.indexOf(elem) == -1) firsts.push(elem)
else if ((first = repeats.indexOf(elem)) == -1) {
repeats.push(elem);
factor *= 2;
} else {
repeats.splice(first, 0, elem);
factor *= repeats.lastIndexOf(elem) - first + 2;
}
}
}
// FIND ALL PERMUTATIONS OF THE FIRSTS USING RECURSION
function permutateFirsts(perm, set) {
if (set.length > 0) {
for (var i = 0; i < set.length; i++) {
var s = set.slice();
var e = s.splice(i, 1);
if (e[0] == abund.elem && s.length < abund.num) continue;
permutateFirsts(perm.concat(e), s, abund);
}
}
else if (repeats.length > 0) {
insertRepeats(perm, repeats);
}
else {
document.write(perm + "<BR>");
++unique;
}
}
// INSERT REPEATS INTO THE PERMUTATIONS USING RECURSION
function insertRepeats(perm, set) {
var abund = abundance(set);
if (perm.length - perm.lastIndexOf(abund.elem) > abund.num) {
var sel = selectElement(perm, set);
var s = set.slice();
var elem = s.splice(sel, 1)[0];
for (var i = perm.lastIndexOf(elem) + 2; i <= perm.length; i++) {
var p = perm.slice();
p.splice(i, 0, elem);
if (set.length == 1) {
document.write(p + "<BR>");
++unique;
} else {
insertRepeats(p, s);
}
}
}
}
// SELECT THE ELEMENT FROM THE SET WHOSE LAST OCCURANCE IN THE PERMUTATION COMES FIRST
function selectElement(perm, set) {
var sel, pos, min = perm.length;
for (var i = 0; i < set.length; i++) {
pos = perm.lastIndexOf(set[i]);
if (pos < min) {
min = pos;
sel = i;
}
}
return(sel);
}
// FIND ABUNDANT ELEMENT AND ABUNDANCE NUMBER
function abundance(set) {
if (set.length == 0) return ({elem: null, num: 0});
var elem = set[0], max = 1, num = 1;
for (var i = 1; i < set.length; i++) {
if (set[i] != set[i - 1]) num = 1
else if (++num > max) {
max = num;
elem = set[i];
}
}
return ({elem: elem, num: 2 * max - set.length});
}
}
seperatedPermutations(["a","b","r","a","c","a","d","a","b","r","a"]);아이디어는 가장 일반적인 것부터 가장 적은 것까지 요소를 정렬하고, 가장 일반적인 것을 취하고, 개수를 줄이고, 내림차순을 유지하면서 목록에 다시 넣는 것입니다 (그러나 가능한 경우 반복을 방지하기 위해 마지막으로 사용한 요소를 먼저 두는 것을 피하는 것입니다) .
이는 Counter및 bisect다음을 사용하여 구현할 수 있습니다 .
from collections import Counter
from bisect import bisect
def unsorted(lst):
# use elements (-count, item) so bisect will put biggest counts first
items = [(-count, item) for item, count in Counter(lst).most_common()]
result = []
while items:
count, item = items.pop(0)
result.append(item)
if count != -1:
element = (count + 1, item)
index = bisect(items, element)
# prevent insertion in position 0 if there are other items
items.insert(index or (1 if items else 0), element)
return result
예
>>> print unsorted([1, 1, 1, 2, 3, 3, 2, 2, 1])
[1, 2, 1, 2, 1, 3, 1, 2, 3]
>>> print unsorted([1, 2, 3, 2, 3, 2, 2])
[2, 3, 2, 1, 2, 3, 2]
- 목록을 정렬하십시오.
- 이 알고리즘을 사용하여 목록의 "최상의 셔플"생성
목록의 최소 항목을 원래 위치 (항목 값 기준)에 제공하므로 예를 들어 정렬 된 위치에서 1, 2, 3을 멀리 놓으려고합니다.
정렬 된 길이 n 목록으로 시작합니다. m = n / 2로합시다. 0, m, 1, m + 1, 2, m + 2 등의 값을 가져옵니다. 동일한 숫자의 절반 이상을 가지지 않는 한 연속 된 순서로 동등한 값을 얻을 수 없습니다.
제 "나도"스타일의 대답을 용서해주세요.하지만 Coady의 대답은 이것 으로 단순화 될 수 없었 나요?
from collections import Counter
from heapq import heapify, heappop, heapreplace
from itertools import repeat
def srgerg(data):
heap = [(-freq+1, value) for value, freq in Counter(data).items()]
heapify(heap)
freq = 0
while heap:
freq, val = heapreplace(heap, (freq+1, val)) if freq else heappop(heap)
yield val
yield from repeat(val, -freq)
편집 : 다음은 목록을 반환하는 파이썬 2 버전입니다.
def srgergpy2(data):
heap = [(-freq+1, value) for value, freq in Counter(data).items()]
heapify(heap)
freq = 0
result = list()
while heap:
freq, val = heapreplace(heap, (freq+1, val)) if freq else heappop(heap)
result.append(val)
result.extend(repeat(val, -freq))
return result
- 각 값이 나타나는 횟수를 계산합니다.
- 가장 빈번한 것부터 가장 적은 빈도로 값을 선택하십시오.
- 선택한 값을 최종 출력에 추가하여 매번 색인을 2 씩 증가시킵니다.
- 인덱스가 경계를 벗어난 경우 인덱스를 1로 재설정
from heapq import heapify, heappop
def distribute(values):
counts = defaultdict(int)
for value in values:
counts[value] += 1
counts = [(-count, key) for key, count in counts.iteritems()]
heapify(counts)
index = 0
length = len(values)
distributed = [None] * length
while counts:
count, value = heappop(counts)
for _ in xrange(-count):
distributed[index] = value
index = index + 2 if index + 2 < length else 1
return distributed
'IT story' 카테고리의 다른 글
| Karma로 nodejs 백엔드 코드를 테스트하는 방법 (Testacular) (0) | 2020.09.14 |
|---|---|
| SimpleDateFormat에 대한 액세스 동기화 (0) | 2020.09.14 |
| UNIQUE 제약 조건이 필드에 INDEX를 자동으로 생성합니까? (0) | 2020.09.14 |
| Node.js에서 만든 웹 사이트를 Github 페이지에 게시하는 방법은 무엇입니까? (0) | 2020.09.14 |
| lock (new object ()) —화물 컬트 또는 미친 "언어 특수 사례"? (0) | 2020.09.14 |