python3で大小関係を考慮した順列の作り方

Question

分からない事

以下のように例えば4個(2N個)の数字が与えられたとして
左側と右側、両方とも必ず数字を小さい順に並びかえたいときの方法が分かりません。

12 34
13 24
14 23
23 14
24 13
34 12

※追記
イメージとして以下の入出力を行いたいです

入力

2

出力

1234
1324
1423
2314
2413
3412

試したこと

itertools のドキュメントで使えそうなものがないか調べましたが上手く行かず。。。

どなたか教えてくださると幸いです！><

Answer 1

こういうことでしょうか？

import sys

data = [
    [int(e) for e in line.split()]
    for line in map(str.rstrip, sys.stdin)
]
print(data)

# 転置して
data = [
    list(col) for col in zip(*data)
]
print(data)

# ソートして
data = [
    sorted(col) for col in data
]
print(data)

# また転置
data = [
    list(row) for row in zip(*data)
]
print(data)

実行結果 Wandbox

[[12, 34], [13, 24], [14, 23], [23, 14], [24, 13], [34, 12]]
[[12, 13, 14, 23, 24, 34], [34, 24, 23, 14, 13, 12]]
[[12, 13, 14, 23, 24, 34], [12, 13, 14, 23, 24, 34]]
[[12, 12], [13, 13], [14, 14], [23, 23], [24, 24], [34, 34]]

コメントを受けて

あんまりクールなコードじゃないですが、いちおう。

from itertools import tee, permutations


def is_already_sorted(iterable, *, key=lambda e: e):
    it1, it2 = tee(iterable)
    return all(
        e1 == e2 for e1, e2 in zip(it1, sorted(it2, key=key))
    )


N = int(input())
assert 0 < 2*N < 10

nums = list('123456789')[:2*N]

dst = []
for e in permutations(nums, 2*N):
    left, right = e[:N], e[N:]
    
    if not is_already_sorted(left, key=int):
        continue
    if not is_already_sorted(right, key=int):
        continue
        
    dst.append(''.join(e))

    
print(*dst, sep='\n')

Wandbox

Comments

[kuraudo]

あっ、、、

上手く伝えることが出来ず申し訳ございません。

自分が一番やりたい事としては
N = 2 と受け取った際に
[[1, 2], [3, 4]]
[[1, 3], [2, 4]]
[[1, 4], [2, 3]]
...
[[3, 4], [1, 2]]

と出力することです..！！

[LouiS0616]

左側n桁、右側n桁の数字列がそれぞれ昇順となるように、
1~2nまでの数字を一回ずつ使って作れる数字列を列挙するってことですね。

[kuraudo]

はい！
全くその通りです。。！

[LouiS0616]

追記しました。
枝切をしていないので計算量は多いですが、暗黙にN<5であることを考えるとそこまで影響は出ないと思います。

[kuraudo]

ありがとうございましたﾟ(ﾟ`ω´ ﾟ)ﾟ
噛み締めて読ませて頂きますm(*_ _)m

Answer 2

概要
・入力例n=3から123456を生成
・123456で作れる全てのパターンを再帰処理で生成
・条件判定OKのものだけリストへ追加
・最後に出力

javaなのであまり参考にならないかもしれません。
n=2,n=3での結果は問題無いはずです。

###出力結果n=3

import java.util.LinkedHashSet;
import java.util.Set;

public class memo_qa146314 {

	public static void main(String[] args) {

		Set<Integer> set = new LinkedHashSet<Integer>();

		//入力省略
		int input = 3;

		String str = "";
		for (int i = 0; i < input * 2; i++) {
			str += Integer.toString(i + 1);
		}
		set = permutation(str, "", set);
		for (int i : set) {
			System.out.println(i);
		}
	}

	public static Set permutation(String q, String ans, Set<Integer> set) {
		if (q.length() == 0) {

			if (chk(ans)) {
				set.add(Integer.parseInt(ans));
			}
			return set;
		} else {
			for (int i = 0; i < q.length(); i++) {
				permutation(q.substring(0, i) + q.substring(i + 1),
						ans + q.charAt(i), set);
			}
		}
		return set;
	}

	private static boolean chk(String ans) {

		boolean result = true;

		String[] h = new String[2];
		h[0] = (ans.substring(0, ans.length() / 2));
		h[1] = (ans.substring(ans.length() / 2));

		int a = 0;
		int b = 0;

		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < h[i].length() - 1; j++) {

				a = Integer.parseInt(h[i].substring(j, j + 1));
				b = Integer.parseInt(h[i].substring(j + 1, j + 2));

				if (a > b) {

					return false;
				}
			}
		}
		return true;
	}
}