Pythonで2進数表現の「1」の個数に基づいて数値をソートするプログラム

数値のリスト nums が与えられたとします。ここで、各数値を2進数表現にしたときの「1」の個数に基づいて、リストを昇順にソートすることを考えます。「1」の個数が同じ数値が複数ある場合は、数値そのものの大小関係に従って並べ替えます。

例えば、入力が nums = [4, 1, 12, 7, 6] の場合、出力は [1, 4, 6, 12, 7] になります。その理由は以下の通りです。

• 4 の2進数表現は 0100
• 1 の2進数表現は 0001
• 6 の2進数表現は 0110
• 12 の2進数表現は 1100
• 7 の2進数表現は 0111

したがって、「1」の個数で並べた結果は [1, 4, 6, 12, 7] となります。1 と 4 はどちらも「1」が1個なので、値の小さい 1 が先に来ます。同様に、6 と 12 も「1」が2個ずつであるため、値の小さい 6 が先に並びます。

解決の手順

この問題を解くには、以下の手順に従います。

• 数値 n を受け取る関数 compare を定義します。
• この関数は、(n の2進数表現における「1」の個数, n の値) というペア（タプル）を返します。
• ソート時に各要素を compare 関数に渡して比較キーとし、nums をソートします。
• ソート済みの nums を返します。

ポイント解説

Pythonでは、組み込み関数 bin() を使うと整数を2進数の文字列（例：'0b100'）に変換できます。さらに、その文字列に対して count("1") を呼び出せば、「1」の出現回数を簡単に数えられます。

また、sort() メソッドの key 引数にタプルを返すラムダ式を指定すると、まずタプルの最初の要素（「1」の個数）で比較され、それが等しい場合には自動的に2番目の要素（値そのもの）で比較されます。これにより、条件を満たすソートをわずか1行で実現できます。

実装例

以下の実装例を見て、理解を深めましょう。

def solve(nums):
    nums.sort(key=lambda num: (bin(num).count("1"), num))
    return nums

nums = [4, 1, 12, 7, 6]
print(solve(nums))

入力

[4, 1, 12, 7, 6]

出力

[1, 4, 6, 12, 7]