プログラミングのお題スレ Part22 (863ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
799(20): デフォルトの名無しさん [sage] 08/16(土)01:44 ID:VU+jlz0U(1/2)
【問題Ａ】
１～９を１つずつ使用して表される９桁の数Anは全部で9!（＝362880）個存在する。
整数n（1≦n≦362880）が与えられたとき、n番目に小さいAnを求めよ。
（例）
1 → 123456789
2 → 123456798
3 → 123456879
123456 → 416589732
234567 → 684753219
362880 → 987654321
【問題Ｂ】
１～４を３つずつ使用して表される12桁の数Bnは全部で12!/(3!)^4（＝369600）個存在する。
整数n（1≦n≦369600）が与えられたとき、n番目に小さいBnを求めよ。
（例）
1 → 111222333444
2 → 111222334344
3 → 111222334434
123456 → 222331434114
234567 → 324424331112
369600 → 444333222111
※求める数値は文字列または各桁の数の配列による表現も可能とする（123⇔"123"⇔[1,2,3]）
800(1): デフォルトの名無しさん [sage] 08/16(土)13:16 ID:MUbLd8/3(1)
>>799 Rust 愚直にn回まわし
use itertools::Itertools; // for tuple_windows()
fn f(init: &str, n: usize) -> String {
let mut list = init.chars().rev().collect::<Vec<_>>();
for _ in 1..n {
if let Some((pre_index, (_, old))) = list.iter().tuple_windows().enumerate().find(|(_, (pre, cur))| pre > cur) {
let old_index = pre_index + 1;
let (new_index, _) = list.iter().enumerate().find(|(_, cur)| cur > &old).unwrap();
list.swap(old_index, new_index);
list[..old_index].reverse();
}
}
list.into_iter().rev().collect()
}
fn main() {
assert_eq!(f("123456789", 1), "123456789");
assert_eq!(f("123456789", 2), "123456798");
assert_eq!(f("123456789", 3), "123456879");
assert_eq!(f("123456789", 123456), "416589732");
assert_eq!(f("123456789", 234567), "684753219");
assert_eq!(f("123456789", 362880), "987654321");
assert_eq!(f("111222333444", 1), "111222333444");
assert_eq!(f("111222333444", 2), "111222334344");
assert_eq!(f("111222333444", 3), "111222334434");
assert_eq!(f("111222333444", 123456), "222331434114");
assert_eq!(f("111222333444", 234567), "324424331112");
assert_eq!(f("111222333444", 369600), "444333222111");
}
801: デフォルトの名無しさん [] 08/16(土)19:14 ID:kN4EEg8M(1/3)
>>799 の問題A
1からnまでの自然数を並べてできるi番目の順列を求める関数を前に作って持っていたので、
それを流用したらすぐできた（元の関数はBigIntとiの範囲外エラーにも対応）。
R
https://ideone.com/hMTf2k
C++
https://ideone.com/ZiU5Aa
802(3): デフォルトの名無しさん [] 08/16(土)20:29 ID:kN4EEg8M(2/3)
>>799 の問題B
R
https://ideone.com/SdWBKf
C++
https://ideone.com/90BpGt
803(1): デフォルトの名無しさん [] 08/16(土)21:32 ID:kN4EEg8M(3/3)
>>799
>>802 のC++のithDuplicatedPermutation関数は引数が別の値（例えばn = 5, m = 3）のとき
正しく計算できなかったので修正。Rの方はintではなくdoubleで計算しているので問題ない。
https://ideone.com/uH8dpO
805(1): デフォルトの名無しさん [sage] 08/17(日)12:07 ID:R1ye1QDy(1/2)
>>799 ruby
https://ideone.com/o2Qlkr
>>799 c
https://ideone.com/Q4XNBb
806(2): 805 [sage] 08/17(日)15:08 ID:R1ye1QDy(2/2)
>>799 ruby 若干の改善
https://ideone.com/oavxRo
>>799 c 若干の改善
https://ideone.com/34A07H
809: デフォルトの名無しさん [] 08/19(火)21:08 ID:zFi0pntB(1)
>>799 問題A
perl
use v5.42;
sub nthPermutation($digits, $rank) {
my @figures = (1..$digits);
my @fact = (1);
push @fact, $_ * $fact[-1] for @figures;
return join "", map { splice(@figures, $_, 1) } sub($n, $r) {
$n-- ? (int($r / $fact[$n]), __SUB__->($n, $r % $fact[$n])) : ();
}->($digits, $rank - 1);
}
for my $i (1, 2, 3, 123456, 234567, 362880) {
say "$i -> " . nthPermutation(9, $i);
}
1 -> 123456789
2 -> 123456798
3 -> 123456879
123456 -> 416589732
234567 -> 684753219
362880 -> 987654321
811(1): 806 [sage] 08/21(木)22:19 ID:fAlkh9Aq(1)
>>799 ruby
https://ideone.com/3TW9Vr
・問題A時に若干端折る
812(5): デフォルトの名無しさん [] 08/21(木)23:15 ID:0KQ1xtxb(1)
>>799 の逆変換プログラム
R
https://ideone.com/TU73Yu
C++
https://ideone.com/dmETd5
問題A, 問題Bとは違って、順列に出現するユニークな整数は1〜nの連番でなくても良いし、
出現回数はすべて同じでなくても良い。例えば、入力は [3, 1, 4, 1, 5, 9] でも良い
（ユニークな整数は1, 3, 4, 5, 9で、出現回数は1が2回、その他が1回）。
813: デフォルトの名無しさん [] 08/22(金)01:14 ID:6LYRfbyj(1)
>>799
Java
https://paiza.io/projects/F5kCIBu6BOVB9QTX7hHWMg
814(1): デフォルトの名無しさん [sage] 08/22(金)06:55 ID:qlaiAqZd(1/2)
>>812
Rust >>799の逆変換の重複順列の何番目か算出
use itertools::Itertools;
use num::{BigUint, One};
// 重複順列の何番目かを求める ex. "222331434114" → "123456"番目
fn to_nth(input: &str) -> String {
// 出現数
let (mut counts, chars): (Vec<usize Vec<char>) = input.chars().sorted().dedup_with_count().multiunzip();
// index化input
let input: Vec<usize> = input.chars().map(|c| chars.iter().position(|&c0| c0 == c).unwrap()).collect();
// 階乗関数
fn factorial(x: usize) -> BigUint { (1..=x).fold(BigUint::one(), |p, x| p * x) }
// 重複順列の総数
let mut whole: BigUint = factorial(input.len()) / counts.iter().map(|&x| factorial(x)).product::<BigUint>();
// nth番目を算出
(1..=input.len()).rev().zip(input).fold(BigUint::one(), |mut nth, (len, index)| {
// 自分より前までの総数をnthに足す
nth += &whole * counts[..index].iter().sum::<usize>() / len;
// 自分の総数へ更新
whole *= counts[index];
whole /= len;
counts[index] -= 1;
nth
})
.to_string()
}
816(1): 811 [sage] 08/22(金)20:26 ID:m9vhyo0Z(1)
>>799 ruby
https://ideone.com/vvp0kq
・問題A時に全体的な規則性に着目
・部分的に着目しちゃったのが>>811
・何も工夫を入れなかったのが>>806
817(1): 816 [sage] 08/23(土)20:27 ID:uyhDG+iz(1/2)
>>799 ruby 問題Bもケア
https://ideone.com/od17Hn
818: デフォルトの名無しさん [sage] 08/23(土)21:01 ID:gxRFdG35(1)
>>799
java
https://ideone.com/qRTy1Z
819(1): 817 [sage] 08/23(土)23:26 ID:uyhDG+iz(2/2)
>>799 java
https://ideone.com/78psr6
821(1): 819 [sage] 08/25(月)00:28 ID:IbSJkZLt(1)
>>799 java Iterable<int[]>
https://ideone.com/NRTZpa
822: デフォルトの名無しさん [sage] 08/27(水)00:40 ID:AbNZa8yo(1/2)
>>799 ocaml
https://ideone.com/1Jx1Q8
>>799 scheme (chicken 4.13)
https://ideone.com/n7pIFw
823: デフォルトの名無しさん [sage] 08/27(水)21:02 ID:AbNZa8yo(2/2)
>>799 octave
https://ideone.com/RH6xXb
825: 821 [sage] 08/28(木)21:01 ID:mnaa+hsk(1)
>>799 java
https://ideone.com/aKkfqN
・next()ごとに複製しない版。する版は >>821
・hasNext()側で次を準備。next()側なのは >>821
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.034s