A word s of lowercase English letters is given on one line. Print every distinct word that uses each letter of s exactly once, in dictionary order (compare from the first letter; the one with the earlier letter comes first), one per line. If s has repeated letters the same word can come up more than once; print it only once (for aab: aab, aba, baa).
Input
1 ≤ length of s ≤ 7
Output
the distinct words, in dictionary order, one per line
Example 1 · stdin
aab
stdout
aab
aba
baa
Example 2 · stdin
cab
stdout
abc
acb
bac
bca
cab
cba
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
One recursion solves both repeats and order. Count how many of each letter are left, and at each position pick one of the remaining letters in order from a, then go down to the next position (put the count back after). Each letter is picked once per position, so the same word never comes up twice, and picking smaller letters first gives dictionary order by itself. Two traps are common. Python itertools.permutations treats positions, not letters, as distinct, so aab yields aab twice. Building by swapping positions does not come out in dictionary order even after removing repeats. Tools differ too. C++ std::next_permutation, started from sorted letters, gives the next permutation in dictionary order without repeats (no recursion); other languages have no such standard function. Seven letters give up to 5,040 lines, so Java and C# collect them in a StringBuilder and write once. In Craykon the function 늘어놓기(prefix) calls itself and returns with return; at the end. It collects the lines in the string out and writes them once with Console.Write(out).
Pythonmain.py · 22 lines
import syss = 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] += 1arrange("")sys.stdout.write("\n".join(out) + "\n")
JavaScriptmain.js · 22 lines
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"));
TypeScriptmain.ts · 24 lines
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"));
JavaMain.java · 31 lines
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); }}
C#Main.cs · 38 lines
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); }}
C++main.cpp · 32 lines
#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;}
Cmain.c · 32 lines
#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;}
Craykonmain.cray · 38 lines
// 같은 글자는 이 자리에서 한 번만 고르니 겹친 줄이 생기지 않고, 작은 글자부터 고르니 사전 순이 된다늘어놓기(prefix){ if (prefix.Length == s.Length) { out += prefix + "\n"; return; } for (i = 0; i < letters.Count; i++) { if (left[i] > 0) { left[i] -= 1; 늘어놓기(prefix + letters[i]); left[i] += 1; } }}s = Console.ReadLine().Trim();// 쓸 수 있는 글자(작은 것부터)와 글자마다 남은 개수letters = [];foreach (c in s){ if (!letters.Contains(c)) { letters.Add(c); }}letters.Sort();left = NewList(letters.Count, 0);foreach (c in s){ left[letters.IndexOf(c)] += 1;}out = "";늘어놓기("");Console.Write(out);