Получить случайные элементы из хеш-таблицы, но сумма значений должна быть равна заданному числу

Question

Я пытаюсь создать простой «распределитель заданий» для домашних заданий между мной и моей женой.Хотя концепция будет очень полезна и на работе, поэтому мне нужно изучить ее правильно.

Моя хеш-таблица:

$Taches = @{
    "Balayeuse plancher" = 20
    "Moppe plancher" = 20
    "Douche" = 15
    "Litières" = 5
    "Poele" = 5
    "Comptoir" = 5
    "Lave-Vaisselle" = 10
    "Toilette" = 5
    "Lavabos" = 10
    "Couvertures lit" = 5
    "Poubelles" = 5
}

Общая стоимость всех элементов составляет 105 (минут).Таким образом, примерно по 50 минут каждому из нас мы делим его на две части.

Моя цель:

Я хочу выбрать случайные элементы из этой хеш-таблицы и создать две разные хеш-таблицы - одну для меня и моей жены, каждая из которых имеетобщая стоимость 50 (так что это справедливо).Например, 20 + 20 + 10 или 5 + 5 + 5 + 15 + 20 и т. Д. Сложная часть заключается в том, что ВСЕ задачи должны учитываться между двумя хеш-таблицами, и они могут присутствовать ОДНАЖДЫ в каждой из них (бесполезно)в очистке одной и той же вещи дважды!).

Какой будет лучший вариант?

На данный момент я успешно достиг случайной хэш-таблицы с общим значением 50, например:

do {
    $Me = $null
    $sum = $null
    $Me = @{}
    $Me = $Taches.GetEnumerator() | Get-Random -Count 5
    $Me | ForEach-Object { $Sum += $_.value }
} until ($sum -eq 50)

Пример результата:

Name                           Value
----                           -----
Poubelles                      5
Balayeuse plancher             20
Douche                         15
Poele                          5
Toilette                       5

Это работает, но мальчик чувствует, что это обходной и изогнутый способ сделать это.Я уверен, что есть лучший подход?Плюс мне не хватает важных вещей.ВСЕ задачи должны быть учтены и не должны присутствовать дважды.Это довольно сложно, хотя сначала это выглядело просто!

Answer 1

Еще один подход:

$MinSum  = ($Taches.Values | Measure-Object -Minimum ).Minimum
$HalfSum = ($Taches.Values | Measure-Object -Sum ).Sum / 2
do {
    $sum = 0
    $All = $Taches.GetEnumerator() | 
        Get-Random -Count $Taches.Keys.Count
    $Me = $All | ForEach-Object { 
        if ( $Sum -lt $HalfSum - $MinSum ) { 
            $Sum += $_.value
            @{ $_.Key = $_.Value }
        }
    }
    Write-Host "$sum " -NoNewline   # debugging output
}  until ($sum -eq 50 )

$Em = $Taches.Keys | ForEach-Object {
    if ( $_ -notin $Me.Keys ) {
        @{ $_ = $Taches.$_ }
    }
}
# show "fairness" (task count vs. task cost) 
$Me.Values | Measure-Object -Sum | Select-Object -Property Count, Sum
$Em.Values | Measure-Object -Sum | Select-Object -Property Count, Sum

Пример вывода (s):

PS D:\PShell> D:\PShell\SO\54610011.ps1
50 
Count Sum
----- ---
    4  50
    7  55

PS D:\PShell> D:\PShell\SO\54610011.ps1
65 65 50 
Count Sum
----- ---
    6  50
    5  55

Answer 2

Вам, вероятно, следует написать алгоритм, чтобы всегда выполнять дополнительное задание при ошибке округления (Happy Wife, Happy Life).

Возможно, это слишком сложная задача, но меня заинтриговал вопрос,и выучил немного французского в процессе.

$Taches = @{
"Balayeuse plancher" = 20
"Moppe plancher" = 20
"Douche" = 15
"Litières" = 5
"Poele" = 5
"Comptoir" = 5
"Lave-Vaisselle" = 10
"Toilette" = 5
"Lavabos" = 10
"Couvertures lit" = 5
"Poubelles" = 5
}

$target = 0
$epsilon = 5

# copy if you don't want to destroy original list (not needed probably)
# put all entries in first list.
# randomly move entry to p2 if count over target +/- epsilon 
# randomly move entry from p2 if count under target +/- epsilon 
# (unless you know you can always get exactly target and not loop forever trying)
$p1 = @{} # person 1
$p2 = @{} # person 2
$p1Total = 0 # optimizaton to not have to walk entire list and recalculate constantly
$p2Total = 0 # might as well track this too...
$Taches.Keys | % {
    $p1.Add($_, $Taches[$_])
    $p1Total += $Taches[$_]
    $target += $Taches[$_]
    }

$target = $target / 2

$done = $false
while (-not $done)
{
    if ($p1Total -gt ($target+$epsilon))
    {
        $item = $p1.Keys | Get-Random
        $value = $p1[$item]
        $p1.Remove($item)
        $p2.Add($item, $value)
        $p1Total -= $value
        $p2Total += $value
        continue
    }
    elseif ($p1Total -lt ($target-$epsilon))
    {
        $item = $p2.Keys | Get-Random
        $value = $p2[$item]
        $p2.Remove($item)
        $p1.Add($item, $value)
        $p1Total += $value
        $p2Total -= $value
        continue
    }

    $done = $true
}

"Final result"
"p1"
$p1Total
$p1

"`np2"
$p2Total
$p2

Answer 3

Отличные ответы, ребята, многому научились.Вот что я в итоге сделал благодаря «Fischfreund» на Reddit (https://www.reddit.com/r/PowerShell/comments/aovs8s/get_random_items_from_hashtable_but_the_total_of/eg3ytds).

. Его подход удивительно прост, но я даже не думал об этом.

Сначалахеш-таблица: Получите случайный счет 5, пока сумма не станет равной 50. Затем создайте вторую хеш-таблицу, в которой элементы не находятся в первой хеш-таблице! Я назначаю эту первую хеш-таблицу, содержащую 5 элементов, моей жене, поэтому я всегда имеюдополнительное задание (как предложено Кори;)).Фу, я в безопасности.

$Taches = @{

    "Balayeuse plancher" = 20
    "Moppe plancher"     = 20
    "Douche"             = 15
    "Litières"           = 5
    "Poele"              = 5
    "Comptoir"           = 5
    "Lave-Vaisselle"     = 10
    "Toilette"           = 5
    "Lavabos"            = 10
    "Couvertures lit"    = 5
    "Poubelles"          = 5

}

do {
$Selection1 = $Taches.GetEnumerator() | Get-Random -Count 5
} until (($Selection1.Value | measure -Sum ).Sum -eq 50)


$Selection2 = $Taches.GetEnumerator() | Where-Object {$_ -notin $Selection1}


$Selection1 | select-object @{Name="Personne";expression={"Wife"} },Name,Value
""
$Selection2 | select-object @{Name="Personne";expression={"Me"} },Name,Value

Answer 4

Вы не можете максимизировать случайность и справедливость одновременно, так что приходится давать.Я думаю, вы не должны рисковать быть несправедливыми по отношению к вашей жене, и поэтому справедливость должна преобладать!

Справедливость за счет случайности

Этот подход сортирует элементы в порядке убывания времени, а затем случайным образом назначает им элементыкаждому человеку, если это назначение не будет несправедливым.

Расчет справедливости здесь заключается в том, что максимальная разница во времени должна составлять самое большее продолжительность самой быстрой задачи.

$DescendingOrder = $Taches.Keys | Sort-Object -Descending { $Taches[$_] }

$Measures = $Taches.Values | Measure-Object -Sum -Minimum
$UnfairLimit = ($Measures.Sum + $Measures.Minimum) / 2

$Person1 = @{}
$Person2 = @{}

$Total1 = 0
$Total2 = 0

foreach ($Item in $DescendingOrder) {

    $Time = $Taches[$Item]
    $Choice = Get-Random 2

    if (($Choice -eq 0) -and (($Total1 + $Time) -gt $UnfairLimit)) {
        $Choice = 1
    }

    if (($Choice -eq 1) -and (($Total2 + $Time) -gt $UnfairLimit)) {
        $Choice = 0
    }

    if ($Choice -eq 0) {
        $Person1[$Item] = $Time
        $Total1 += $Time
    } else {
        $Person2[$Item] = $Time
        $Total2 += $Time
    }
}

Пример выполнения:

PS> $Person1 | ConvertTo-Json

{
    "Comptoir":  5,
    "Lavabos":  10,
    "Litières":  5,
    "Couvertures lit":  5,
    "Douche":  15,
    "Lave-Vaisselle":  10
}

и другое лицо:

PS> $Person2 | ConvertTo-Json

{
    "Moppe plancher":  20,
    "Toilette":  5,
    "Balayeuse plancher":  20,
    "Poubelles":  5,
    "Poele":  5
}

Случайность за счет справедливости

Этот подход заключается в рандомизации списка, просмотре каждого элемента и назначенииэто человеку, которому на данный момент отведено наименьшее количество времени.

Более ранние решения могут означать, что более поздние решения оказываются несправедливыми.

$RandomOrder = $Taches.Keys | Sort-Object { Get-Random }

$Person1 = @{}
$Person2 = @{}

$Total1 = 0
$Total2 = 0

foreach ($Item in $RandomOrder) {

    $Time = $Taches[$Item]

    if ($Total1 -lt $Total2) {
        $Person1[$Item] = $Time
        $Total1 += $Time
    } else {
        $Person2[$Item] = $Time
        $Total2 += $Time
    }
}

Пример выполнения:

PS> $Person1 | ConvertTo-Json

{
    "Poele":  5,
    "Douche":  15,
    "Couvertures lit":  5,
    "Lave-Vaisselle":  10,
    "Balayeuse plancher":  20,
    "Toilette":  5
}

и другой человек:

PS> $Person2 | ConvertTo-Json

{
    "Lavabos":  10,
    "Comptoir":  5,
    "Poubelles":  5,
    "Litières":  5,
    "Moppe plancher":  20
}