文字の並べ方
英小文字でできた単語 s が一行で与えられる。
s の文字をすべて一回ずつ使って作れる異なる単語を、辞書順（先頭の文字から比べ、アルファベットが前のほうが先）に一行に一つずつすべて出力せよ。
s に同じ文字が複数あると同じ単語が何度もできることがあるが、一度だけ出力する（aab なら aab、aba、baa）。
- 入力
- 1 ≤ s の長さ ≤ 7
- 出力
- 異なる単語を辞書順に一行に一つ
aab
aab aba baa
cab
abc acb bac bca cab cba
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
一つの再帰で重なりと順番を同時に解決します。
文字ごとに残りの個数を数えておき、位置ごとに「残っている文字のうち一つ」を a から順に選んで次の位置へ下ります（選んだ後は個数を戻します）。
同じ文字は一つの位置で一度しか選ばないので同じ単語はもう生まれず、小さい文字から選ぶので自然に辞書順になります。
よくある罠は二つです。
Python itertools.permutations は文字ではなく位置を区別するので、aab から aab が二回出ます。
位置の入れ替え（swap）で作る方法は、重なりを消しても辞書順になりません。
道具も言語によって違います。
C++ std::next_permutation は整列した文字から始めると、重なりなしに辞書順で次の順列をくれます（再帰なし）。
他の言語にはこのような標準関数はありません。
7 文字なら最大 5,040 行なので、Java・C# は StringBuilder に集めて一度に書きます。
Craykon は関数 늘어놓기(prefix) が自分自身を呼び、最後まで行くと 返す; で戻ります。
行は文字列 out に集めて コンソール.続けて書く(out) で一度に書きます。
import sys s = input().strip()letters = sorted(set(s)) # 쓸 수 있는 글자(작은 것부터)left = {c: s.count(c) for c in letters} # 글자마다 남은 개수out = [] def arrange(prefix): if len(prefix) == len(s): out.append(prefix) return # 같은 글자는 이 자리에서 한 번만 고르니 겹친 줄이 생기지 않고, 작은 글자부터 고르니 사전 순이 된다 for c in letters: if left[c] > 0: left[c] -= 1 arrange(prefix + c) left[c] += 1 arrange("")sys.stdout.write("\n".join(out) + "\n")const s = require("fs").readFileSync(0, "utf8").trim();const letters = [...new Set(s)].sort(); // 쓸 수 있는 글자(작은 것부터)const left = new Map(letters.map((c) => [c, [...s].filter((x) => x === c).length]));const out = []; function arrange(prefix) { if (prefix.length === s.length) { out.push(prefix); return; } // 같은 글자는 이 자리에서 한 번만 고르니 겹친 줄이 생기지 않고, 작은 글자부터 고르니 사전 순이 된다 for (const c of letters) { if (left.get(c) > 0) { left.set(c, left.get(c) - 1); arrange(prefix + c); left.set(c, left.get(c) + 1); } }} arrange("");console.log(out.join("\n"));import { readFileSync } from "node:fs";const s: string = readFileSync(0, "utf8").trim();const letters: string[] = [...new Set(s)].sort(); // 쓸 수 있는 글자(작은 것부터)const left = new Map<string, number>(letters.map((c) => [c, [...s].filter((x) => x === c).length]));const out: string[] = []; function arrange(prefix: string): void { if (prefix.length === s.length) { out.push(prefix); return; } // 같은 글자는 이 자리에서 한 번만 고르니 겹친 줄이 생기지 않고, 작은 글자부터 고르니 사전 순이 된다 for (const c of letters) { const k = left.get(c)!; if (k > 0) { left.set(c, k - 1); arrange(prefix + c); left.set(c, k); } }} arrange("");console.log(out.join("\n"));import java.util.Scanner; public class Main { static int[] left = new int[26]; // 글자마다 남은 개수 static char[] path; static StringBuilder out = new StringBuilder(); static void arrange(int depth) { if (depth == path.length) { out.append(path).append('\n'); return; } // 같은 글자는 이 자리에서 한 번만 고르니 겹친 줄이 생기지 않고, a부터 고르니 사전 순이 된다 for (int c = 0; c < 26; c++) { if (left[c] > 0) { left[c]--; path[depth] = (char) ('a' + c); arrange(depth + 1); left[c]++; } } } public static void main(String[] args) { String s = new Scanner(System.in).next(); for (char ch : s.toCharArray()) left[ch - 'a']++; path = new char[s.length()]; arrange(0); System.out.print(out); }}using System;using System.Text; class Program{ static int[] left = new int[26]; // 글자마다 남은 개수 static char[] path; static StringBuilder output = new StringBuilder(); static void Arrange(int depth) { if (depth == path.Length) { output.Append(path).Append('\n'); return; } // 같은 글자는 이 자리에서 한 번만 고르니 겹친 줄이 생기지 않고, a부터 고르니 사전 순이 된다 for (int c = 0; c < 26; c++) { if (left[c] > 0) { left[c]--; path[depth] = (char)('a' + c); Arrange(depth + 1); left[c]++; } } } static void Main() { string s = Console.ReadLine().Trim(); foreach (char ch in s) left[ch - 'a']++; path = new char[s.Length]; Arrange(0); Console.Write(output); }}#include <array>#include <iostream>#include <string> std::array<int, 26> left{}; // 글자마다 남은 개수std::string path, out; void arrange(std::size_t depth) { if (depth == path.size()) { out += path; out += '\n'; return; } // 같은 글자는 이 자리에서 한 번만 고르니 겹친 줄이 생기지 않고, a부터 고르니 사전 순이 된다 for (int c = 0; c < 26; c++) { if (left[c] > 0) { left[c]--; path[depth] = static_cast<char>('a' + c); arrange(depth + 1); left[c]++; } }} int main() { std::string s; std::cin >> s; for (char ch : s) left[ch - 'a']++; path.assign(s.size(), ' '); arrange(0); std::cout << out;}#include <stdio.h>#include <string.h> static int left[26]; // 글자마다 남은 개수static char path[8];static int n; static void arrange(int depth) { if (depth == n) { puts(path); return; } // 같은 글자는 이 자리에서 한 번만 고르니 겹친 줄이 생기지 않고, a부터 고르니 사전 순이 된다 for (int c = 0; c < 26; c++) { if (left[c] > 0) { left[c]--; path[depth] = 'a' + c; arrange(depth + 1); left[c]++; } }} int main(void) { char s[8]; scanf("%7s", s); n = strlen(s); for (int i = 0; i < n; i++) left[s[i] - 'a']++; path[n] = '\0'; arrange(0); return 0;}// 같은 글자는 이 자리에서 한 번만 고르니 겹친 줄이 생기지 않고, 작은 글자부터 고르니 사전 순이 된다늘어놓기(prefix){ もし (prefix.長さ == s.長さ) { out += prefix + "\n"; 返す; } 繰り返す (i = 0; i < letters.個数; i++) { もし (left[i] > 0) { left[i] -= 1; 늘어놓기(prefix + letters[i]); left[i] += 1; } }} s = コンソール.行読み().空白除去();// 쓸 수 있는 글자(작은 것부터)와 글자마다 남은 개수letters = [];それぞれ (c の中 s){ もし (!letters.含む(c)) { letters.追加(c); }}letters.並べ替え();left = 新リスト(letters.個数, 0);それぞれ (c の中 s){ left[letters.位置検索(c)] += 1;}out = "";늘어놓기("");コンソール.続けて書く(out);