在O（n）中的Perl中对列表进行自定义的重新排序/排序

用户名

我正在重新排序列表。

我的OrignalList，输入：@lineItems

[
  {id=> 'id1', ..},
  {id=> 'id2', 'groupId'=>45D,.. },
  {id=> 'id3', 'groupId'=>56A, .. },
  {id=> 'id4', 'groupId'=>45D, 'isParent'=>1 .. },
  {id=> 'id5', ..},
  {id=> 'id6', 'groupId'=>56A, 'isParent'=>1.. },
]

在上面的列表中，groupId表示该项目是捆绑包的一部分。GroupId唯一确定捆绑包组。如果组ID不存在，则其为非捆绑商品。

目的-重新排序列表，以便在每个捆绑包的开始处将所有捆绑包项目与父项分组在一起，捆绑包和非捆绑包项目（当不存在groupId时）的传入顺序应保持不变。对O（n）中的列表进行排序

预期产量：

    [
     {id=> 'id1', ..},
     {id=> 'id4', 'groupId'=>45D, 'isParent'=>1 .. },
     {id=> 'id2', 'groupId'=>45D,.. },
     {id=> 'id6', 'groupId'=>56A, 'isParent'=>1.. },
     {id=> 'id3', 'groupId'=>56A, .. },
     {id=> 'id5', ..},
    ]

这是我的算法：

创建一个id = @sortedLineitemsIds的sortedList
使用sortedIdsList形成最终的排序列表

＃1的代码

        my $grouIdToLineItemIdMap;

        foreach my $lineItem (@$lineItems) {
            if(!$lineItem->{'groupID'}) { #non bundle item, add as it is
                push @sortedLineitemsIds, $lineItem->{'id'};
            } else {
                if($lineItem->{'IsParent'} eq 1) {
                    unshift @{$grouIdToLineItemIdMap->{$groupId}}, $lineItem->{'id'};
                } else {
                    push @{$grouIdToLineItemIdMap->{$groupId}}, $lineItem->{'id'};
                }
            }
        }

        push @sortedLineitemsIds, $grouIdToLineItemIdMap; # **[[Question 1]]** This will always add bundle items at the end irrespective of whether it was in starting or end.

现在这将产生sortedLineitemsIds =>

    $VAR1 = [
     'id1',
     'id5',
     {
      '45D' => [
        'id4:',
        'id2:'
       ],
      '56A' => [
        'id6:',
        'id3:'
      ]
     }
   ];

＃2的代码

    foreach my $Id (@sortedLineitemsIds) {
        if(determineIfSingleIdOrMapOfGroupId) { #**[[Question 2]]**
            my $lineItem = grep @lineItems with $Id; #**[[Question 3]]**
            push @sortedLineItems, $lineItem;
        } else {
             my $listOfLineItemsForGroupId = $sortedLineitemsIds->{$Id};
             foreach groupLineItemId (@$listOfLineItemsForGroupId) {
                 my $lineItem = grep @lineItems with groupLineItemId; #**[[Question 3]]**
                 push @sortedLineItems, $lineItem;
             }
        }
    }

我现在在代码中的不同位置上面标记了3个问题：

问题1->在这里，我不想更改项目的传入顺序。只是分组。但是我正在做的是将组中的所有lineItem推送到map中，我将在循环结束时追加到该行。我怎样才能在循环中做到这一点以保持顺序？
问题2->如何确定是单个ID（非捆绑ID）还是groupID（基本上是包含lineItemIds的引用）？
问题3->如何基于'id'grep原始列表并获取相应的lineItem？

池上

您说您不想更改项目的顺序，但这显然是不正确的。我将假设您的意思是：

我想保留独立项目或组别中项目的相对顺序。

实际上，这可以在O（N）中完成。

我们将构建这个：

my @grouped = (
    [ $lineItem_id1 ],
    [ $lineItem_id4, $lineItem_id2 ],
    [ $lineItem_id6, $lineItem_id3 ],
    [ $lineItem_id5 ],
);

为此，我们将使用以下算法：

对于每个项目，
1. 如果项目是独立的，
  1. 将其添加到@grouped。
2. 其他，
  1. 查找是否曾经遇到过该项目的组。
  2. 如果该商品属于我们之前从未遇到过的商品，
    1. 如果是父母
      1. 将其添加到现有组的开始。
    2. 其他，
      1. 将其添加到现有组的末尾。
  3. 其他，
    1. 从项目创建一个新组。
    2. 将新组添加到@grouped。
    3. 将新组添加到查找哈希。

最后，我们将得出以下结果：

my $group_45D = [ $lineItem_id4, $lineItem_id2 ];
my $group_56A = [ $lineItem_id6, $lineItem_id3 ];

my %groups = (
   '45D' => $group_45D,
   '56A' => $group_56A,
);

my @grouped = (
    [ $lineItem_id1 ],
    $group_45D,
    $group_56A,
    [ $lineItem_id5 ],
);

解：

my @grouped;
{
   my %groups;
   for my $lineItem (@$lineItems) {
      if ( my $groupId = $lineItem->{groupId} ) {
         if (!$groups{$groupId}) {
            push @grouped, $groups{$groupId} = [];
         }

         if ($lineItem->{isParent}) {
             unshift @{ $groups{$groupId} }, $lineItem;
         } else {
             push @{ $groups{$groupId} }, $lineItem;
         }
      } else {
         push @grouped, [ $lineItem ];
      }
   }
}

最后，我们只需要整理列表即可。