受け取った課題に問題があり、問題のテキストに欠陥があると確信しています。私はこれを次のように翻訳しました：
{1,2,..,m}、m < n の要素を持つリスト x[1..2n] を考えてみましょう。すべての要素が単一のペアに存在するように、要素をペア (i < j の (x[i],x[j]) のペア) にグループ化する O(n) の複雑さを持つアルゴリズムを Python で提案および実装します。 . ペアの各セットについて、ペアの最大合計を計算し、それを残りのセットと比較します。それらの最小値を持つセットを返します。
For example, x = [1,5,9,3] can be paired in three ways:
(1,5),(9,3) => Sums: 6, 12 => Maximum 12
(1,9),(5,3) => Sums: 10, 8 => Maximum 10
(1,3),(5,9) => Sums: 4, 14 => Maximum 14
----------
Minimum 10
Solution to be returned: (1,9),(5,3)
不思議に思う点は以下のとおりです。
表内容定義の要素があると言う
1..2n, from {1..m}, m < n。しかし、 の場合m < n、一部を複製せずにリストに入力するのに十分な要素がありません。これは許可されていません。それで、私は仮定しm >= 2nます。また、この例ではn = 21より大きい要素を使用していますが、それが意味していると思います。O（n）の複雑さ？それらを単一のループに結合する方法はありますか？何も考えられません。
私の計算:
For n = 4:
Number of ways to combine: 6
Valid ways: 3
For n = 6
Number of ways to combine: 910
Valid ways: 15
For n = 8
Number of ways to combine: >30 000
Valid ways: ?
したがって、明らかに、ブルートフォースを使用して、それが有効かどうかを判断することはできません。可能な方法の合計を計算するために使用した式は次のとおりです。
C(C(n,2),n/2)
質問：
この問題は間違って書かれており、解決できませんか? もしそうなら、それを実現可能にするために、どのような条件を追加または削除する必要がありますか? Python でいくつかのコードを提案する場合は、事前に作成された関数を使用できないことを覚えておいてください。ありがとうございました