Расчет всех возможных комбинаций людей в гостиничных номерах
Учитывая, что у меня есть следующая комбинация людей, желающих остаться в отеле;
- 3 взрослых
- 6 детей
Как я могу рассчитать все различные комбинации комнат, которые можно выбрать на основе вышеизложенного, когда ребенок не может быть один в комнате, и все люди должны быть использованы? (Примечание: это в приложении PHP).
Например, вышеупомянутое могло быть сломано как;
- 1 комната со всеми в
- 2 комнаты с;
- 1 взрослый 6 детей
- 1 взрослый 0 детей
- 2 комнаты с;
- 1 взрослый 5 детей
- 1 взрослый 1 ребенок
- так далее…
В идеале это должно привести к структуре данных в соответствии с;
[
// Room combination
[
// Individual Room
[
'adults' => 3,
'children' => 6
]
],
[
[
'adults' => 2,
'children' => 5
],
[
'adults' => 1,
'children' => 0
]
]
]
У меня есть следующий код, который работает со взрослыми, но я не могу думать, как ввести в это понятие детей.
public function partition($left, $last = 1, $ar = [], &$partitions = [])
{
if ($left == 0) {
array_push($partitions, $ar);
}
for ($n = $last; $n <= $left; $n++) {
$b = $ar;
array_push($b, $n);
array_merge($partitions, $this->partition($left - $n, $n, $b, $partitions));
}
return $partitions;
}
Решение
В поисках перестановки?
function perm($pool,$result=array())
{
if(empty($pool))
{
echo implode(' ',$result).'<br>';
}else
{
foreach($pool as $key => $value)
{
$neuerpool = $pool;
$neuerresult = $result;
$neuerresult[]= $value;
unset($neuerpool[$key]);
perm($neuerpool,$neuerresult);
}
}
}perm(array('der hund ','übersprang ','den graben ','mit einem weiten sprung '));
Скопировано из http://phpforum.de/forum/showthread.php?t=210119
Другие решения
У меня была такая же проблема, но мы работали со Scala, я видел его пост во время его разработки, я думаю, что мы пытались преобразовать его решение по одному, а затем с помощью некоторых языковых инструментов мы могли бы преобразовать и объединить, я не знаю, если он может попытаться воспроизвести нечто подобное в php, я не знаю, является ли это наиболее эффективным способом, но он работает довольно быстро:
import scala.collection.mutable.ListBuffer
object example extends App {
case class Room(cant: Int, tipo: String) {
override def toString: String = " " + cant + "" + tipo
}
val tagAdults = " adult(s) "val emptyAdult = Room(0, tagAdults)
val tagChildren = " child(s) "val emptyChild = Room(0, tagChildren)
def perm(x: Room): Seq[List[Room]] = (1 to x.cant).map { i =>
val result = new ListBuffer[Room]()
var total = x.cant / i
while (total > 0) {
if ((result.map(_.cant).sum + i) <= x.cant) result += Room(i, x.tipo)
total -= 1
}
if (x.cant % i > 0) result += Room(x.cant % i, x.tipo)
result.toList
}
val adults = perm(Room(3, tagAdults))
val childrens = perm(Room(5, tagChildren))
val combinators = for {
x <- adults
y <- childrens.filter(_.length <= adults.map(_.length).max)
} yield x zipAll(y, emptyAdult, emptyChild)
val cleanAdultsBeginZero = combinators.filter(_.forall(_._1.cant > 0))cleanAdultsBeginZero.sortBy(_.length).foreach { x =>
val tag = "room(s)"
println(s"${x.length} $tag")
x.groupBy { case (room1, room2) => room1.cant + room2.cant }.foreach { case (key, rooms) =>
println(rooms.length + " " + tag + " of " + key + " people " + rooms.head)
}
println()
}
}
Можете ли вы проверить этот код в:
jdoodle или же
scastie
Предварительный просмотр одного рабочего листа scala:
detector