从哈希表中获取随机项目，但总价值必须等于给一组号码

问题描述 投票：3回答：4

我试图建立一个简单的“任务分配”我和我妻子之间的房子的任务。虽然这个概念在工作中会很有用太，所以我需要好好学学吧。

我的哈希表：

$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等硬的部分是，所有的任务有两个哈希表之间进行占和它们只能在它们中的每存在ONCE（没有用清洗同样的事情两次！）。

什么是最好的选择？

现在我成功地实现了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

它的工作原理，但男孩它觉得这是一种迂回的和做的歪路。我敢肯定有一个更好的办法？加上我缺乏重要的事情。所有的任务都必须考虑，并不会出现两次。这是相当复杂的，尽管它起初看起来简单！

powershell random max hashtable
4个回答
4
投票

你不能在同一时间最大化的随机性和公平性这样一个必须给。我想你不应该冒着被不公平的，你的妻子，因此必须公平为准！

Fairness at the expense of randomness

这种方法在递减时间顺序排序的项目，然后随机分配他们的项目，以每个人，除非该任务将是不公平的。

这里的公平的计算是，最大时间差应该是最多最快任务的持续时间。

$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
}

Randomness at the expense of fairness

这种方法是随机的名单，经过每个项目，然后将其分配给谁了分配给他们到目前为止最少的时间的人。

早先的决定可能意味着以后的决策最终是不公平的。

$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
}
2
投票

你或许应该写算法总是有你采取额外的任务舍入误差（快乐的妻子，幸福生活）。

这可能是过度设计，但我对这个问题很感兴趣，并且在这个过程中学会了一些法语。

$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
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

样品输出（一个或多个）：

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
0
投票

伟大的答案家伙，学到了很多东西。以下是我最后做感谢Reddit上“Fischfreund”（https://www.reddit.com/r/PowerShell/comments/aovs8s/get_random_items_from_hashtable_but_the_total_of/eg3ytds）。

他的做法是非常简单但我没想到它。

首先哈希表：获得5随机数，直到总和为50。然后创建一个哈希表二在项目不是在第一哈希表！我指定一个包含5项我的妻子，首先hahstable所以我是一个谁总是有一个额外的任务（如由Kory建议;））。呼我很安全。

$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
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.