Created
January 14, 2022 06:20
-
-
Save nineclue/d2b95528e694b45ece534da8fca7cbef to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def distribute[A](select: Seq[A], slot: Int) = { | |
| val total = select.length | |
| // slot에 나누기 위해 선택해야 하는 slot의 최소수 | |
| val tmin = total / slot + (if (total % slot == 0) 0 else 1) | |
| // slot에 나눌수 있는 slot의 최대수 | |
| val tmax = total - slot + 1 | |
| (tmin to tmax).map({ tn => | |
| /* 가능한 순서들을의 조합 | |
| 뒤 slot에서 앞 slot보다 많은 item을 담을 수는 없다 | |
| slot간의 순서는 관계없다 | |
| 앞 slot에서 Seq의 앞부분에서 가능한 갯수를 선택하고 다음 slot에서 선택하는 방식으로 구한다 | |
| si : 현재 선택하는 slot | |
| remain : 남은 items | |
| taken : 이전 slot에서 선택한 items | |
| 반환 : Seq[A] - 한 slot에 담은 items | |
| Seq[Seq[A]] - slot들에 배분된 items, length == slot | |
| Seq[Seq[Seq[A]]] - 최대 tn개를 담을 수 있을 때 가능한 조합들 | |
| Seq[Seq[Seq[Seq[A]]]] - 전체에서 배분가능한 조합 | |
| */ | |
| def h(si: Int, remain: Seq[A], taken: Seq[Seq[A]]): Seq[Seq[Seq[A]]] = { | |
| if (remain.length == (slot - si)) | |
| Seq(taken ++ remain.map(s => Seq(s))) | |
| else { | |
| val tnum = tn min (remain.length - (slot - si) + 1) | |
| val takens = remain.combinations(tnum).toSeq | |
| takens.flatMap(t => h(si + 1, remain.filterNot(t.contains), taken :+ t)) | |
| } | |
| } | |
| h(0, select, Seq.empty) | |
| }) | |
| } | |
| val jobs = Seq("A", "B", "C", "D", "E", "F", "G") | |
| distribute(jobs, 4) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment