时间戳

首页 > 解决方案 > 交错按列排序的行

linux - 交错按列排序的行

问题描述

（类似于How to interleave lines from two text files but for a single input。也类似于按组和列排序行，但交错或随机化与排序。）

我在两列中有一组系统和任务SYSTEM,TASK：

alpha,90198500
alpha,93082105
alpha,30184438
beta,21700055
beta,33452909
beta,40850198
beta,82645731
gamma,64910850

我想以平衡的方式将任务分配给每个系统。每个系统具有相同数量的任务的理想情况是循环，一个alpha然后一个，beta然后一个，然后gamma重复直到完成。

我可以用一些花哨的脚本来很好地解决这个问题，将数据拆分成多个文件（grep ^alpha, input > alpha.txt等），然后用paste或类似的方式重新组合它们，但我想使用单个命令或一组管道来运行它而无需中间文件或适当的脚本语言。仅使用就可以sort -R让我完成 95% 的工作，但我几乎每次都会为同一系统连续执行 2 个任务，有时会执行 3 个或更多任务，具体取决于初始分布。

system编辑：为了澄清，任何输出在连续两行中都不应该相同。必须保留所有system,task对，您不能将任务从一个系统移动到另一个系统 - 这会使这变得非常容易！

几个可能的示例输出之一：

beta,40850198
alpha,90198500
beta,82645731
alpha,93082105
gamma,64910850
beta,21700055
alpha,30184438
beta,33452909

标签： linuxbashcommand-line

解决方案

我们首先回答潜在的理论问题。问题并不像看起来那么简单。随意根据这个答案实现一个脚本。

格式化为引号的块不是引号。我只是想在这个相当长的答案中突出显示它们以改善导航。

理论问题

给定频率为 f : L→ℕ 0的字母 L 的有限集合，找到一个字母序列，使得每个字母 ℓ 恰好出现 f(ℓ) 次并且序列的相邻元素总是不同的。

例子

L = {a,b,c} 其中 f(a)=4, f(b)=2, f(c)=1

  • ababaca、acababa 和 abacaba 都是有效的解决方案。
  • aaaabbc 无效 – 一些相邻元素相等，例如 aa 或 bb。
  • ababac 无效 – 字母 a 出现 3 次，但频率为 f(a)=4
  • cababac 无效 – 字母 c 出现 2 次，但频率为 f(c)=1

解决方案

当且仅当存在解决方案时，以下方法会产生有效序列。

  1. 按频率对字母进行排序。
    为便于记号，我们假设 f(a) ≥ f(b) ≥ f(c) ≥ ... ≥ 0。
    注意：存在解当且仅当 f(a) ≤ 1 + ∑<sub>ℓ≠af(ℓ)。
  2. 写下 f(a) 很多 a 的序列 s。
  3. 将剩余的字母添加到 FIFO 工作列表中，即：
    • （不要添加任何a）
    • 首先添加 f(b) 很多 b
    • 那么 f(c) 很多 c
    • 等等
  4. 从左到右遍历序列 s 并在每个元素后插入工作列表中的一个字母。重复此步骤，直到工作列表为空。

例子

L = {a,b,c,d} 其中 f(a)=5, f(b)=5, f(c)=4, f(d)=2

  1. 字母已经按频率排序。
  2. s = aaaaa
  3. 工作清单 = bbbbbccccdd。最左边的条目是第一个条目。
  4. 我们从左到右迭代。我们从工作列表中插入字母的地方用 _ 下划线标记。
    • s = a_a_a_a_a_ workinglist = bbbbbccccdd
      s = aba_a_a_a_ workinglist = bbbbccccdd
      s = ababa_a_a_ workinglist = bbbccccdd
      ...
      s = ababababab workinglist = ccccdd
      ⚠️ 我们到达了序列 s 的末尾。我们重复第 4 步。
    • s = a_b_a_b_a_b_a_b_a_b_ workinglist = ccccdd
      s = acb_a_b_a_b_a_b_a_b_ workinglist = cccdd
      ...
      s = acbcacb_a_b_a_b_a_b_ workinglist = cdd
      s = acbcacbca_b_a_b_a_b_ workinglist = dd
      s = acbcacbcadb_a_b_a_b_ workinglist = d
      s = acbcacbcadbda_b_a_b_ workinglist =
      ⚠️ The working list is empty. 我们停下来。
  5. 最后的序列是 acbcacbcadbdabab。

在 Bash 中实现

这是bash与您的输入格式一起使用的建议方法的实现。每行都没有使用工作列表，而是用二进制浮点数标记，指定该行在最终序列中的位置。然后这些行按它们的标签排序。这样我们就不必使用显式循环。中间结果存储在变量中。不创建文件。

#! /bin/bash
inputFile="$1" # replace $1 by your input file or call "./thisScript yourFile"

inputBySys="$(sort "$inputFile")"
sysFreqBySys="$(cut -d, -f1 <<< "$inputBySys" | uniq -c | sed 's/^ *//;s/ /,/')"
inputBySysFreq="$(join -t, -1 2 -2 1 <(echo "$sysFreqBySys") <(echo "$inputBySys") | sort -t, -k2,2nr -k1,1)"

maxFreq="$(head -n1 <<< "$inputBySysFreq" | cut -d, -f2)"
lineCount="$(wc -l <<< "$inputBySysFreq")"
increment="$(awk '{l=log($1/$2)/log(2); l=int(l)-(int(l)>l); print 2^l}' <<< "$maxFreq $lineCount")"

seq="$({ echo obase=2; seq 0 "$increment" "$maxFreq" | head -n-1; } | bc |
        awk -F. '{sub(/0*$/,"",$2); print 0+$1 "," $2 "," length($2)}' |
        sort -snt, -k3,3 -k2,2 | head -n "$lineCount")"

paste -d, <(echo "$seq") <(echo "$inputBySysFreq") | sort -nt, -k1,1 -k2,2 | cut -d, -f4,6

由于seq和awk.

推荐阅读