Блог

У меня есть хэш-таблица, которая имитирует эту таблицу. Так, например, $ h [‘C’]. C сопоставляется с 3, $ h [‘A’] .A соответствует 1

Я хотел бы выполнить итерацию по таблице, чтобы найти группировки. Например, вывод будет следующим:
A
B, C
D

A и D находятся на своей собственной строке, поскольку в столбце или строке есть только одна запись без нуля.
B и C вместе, поскольку их столбец и / или строка пересекаются с числом, большим нуля.
Я думаю, что решение должно включать некоторый тип рекурсии.

У меня есть это, но я думаю, что мне нужно рекурсивно вызвать его

 foreach($i in $h.GetEnumerator()){
   $Results = 'Groups'
   foreach($t in $h.GetEnumerator()){
            $iString = $i.Name
            $tString = $t.Name
            if($h[$iString].$tString -ne '0'){
               if($iString -eq $tString){
                    $Results  = ',' $tString 
               }
               else{
                #recursive call
               }
            }
   }
   $Results
}
 

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

Затем вы пытаетесь найти все связанные компоненты, которые представляют собой наборы узлов в каждом отдельном подграфе.

Вы можете превратить свою хеш-таблицу в список ребер в ориентированном графе следующим образом:

 $data = [ordered] @{
    "A" = [ordered] @{
        "A" = 1
        "B" = 0
        "C" = 0
        "D" = 0
    }
    "B" = [ordered] @{
        "A" = 0
        "B" = 5
        "C" = 2
        "D" = 0
    }
    "C" = [ordered] @{
        "A" = 0
        "B" = 2
        "C" = 3
        "D" = 0
    }
    "D" = [ordered] @{
        "A" = 0
        "B" = 0
        "C" = 0
        "D" = 2
    }
}

$nodes = $data.GetEnumerator() | foreach-object { $_.Key };
$edges = $data.GetEnumerator() | foreach-object {
    $start = $_.Key;
    $_.Value.GetEnumerator() | foreach-object {
        if( $_.Value -ne 0 )
        {
            write-output (new-object PSCustomObject -Property ([ordered] @{
                "Start" = $start
                "End"   = $_.Key
            }));
        }
    }
};

write-host ($nodes | format-list * | out-string);
# A
# B
# C
# D

write-host ($edges | format-table | out-string);
# Start End
# ----- ---
# A     A
# B     B
# B     C
# C     B
# C     C
# D     D
 

Затем вам «просто» нужно выполнить несколько поисков в глубину, чтобы найти подграфы…

 # based on the non-recursive pseudocode at
# https://en.wikipedia.org/wiki/Depth-first_search#Pseudocode

$subgraphs = new-object System.Collections.ArrayList;

$unvisited = new-object System.Collections.ArrayList;
$unvisited.AddRange($nodes);

while( $unvisited.Count -gt 0 )
{

    $subgraph = @();
    $node     = $unvisited[0];

    # let S be a stack
    $stack = new-object System.Collections.Generic.Stack[string];

    # S.push(v)
    $stack.Push($node);

    # while S is not empty do
    while( $stack.Count -gt 0 )
    {

        # v = S.pop()
        $node = $stack.Pop();

        # if v is not labeled as discovered then
        if( $unvisited -contains $node )
        {

            # label v as discovered
            $unvisited.Remove($node);

            # for all edges from v to w in G.adjacentEdges(v) do
            $adjacents = $edges | where-object { $_.Start -eq $node };
            foreach( $adjacent in $adjacents )
            {
                # S.push(w)
                $stack.Push($adjacent.End);
            }

            $subgraph  = $node;

        }
    }

    $null = $subgraphs.Add($subgraph);

}
 

что дает следующие результаты:

 foreach( $subgraph in $subgraphs )
{
    write-host $subgraph
}
# A
# B C
# D
 

Примечание — не проверялось ни для каких наборов данных, кроме того, который указан в вопросе!