156(10): デフォルトの名無しさん [sage] 2023/11/25(土) 20:07:06.40 ID:zpqT0hBE(1) AAS
お題：ランダムに1から9999までの整数を得た時、何回で全種類出揃うか確認せよ
擬似乱数列生成法については指定しないものとする

ruby
外部ﾘﾝｸ:ideone.com
require 'set'
r = 1..9999
c = r.to_a.fill(0)
s = r.to_set
while !s.empty?
n = rand(r)
c[n - r.first] += 1
s.delete n
end
p c.sum
↓
84736

171(5): デフォルトの名無しさん [sage] 2023/11/30(木) 06:46:26.20 ID:/rzYr39l(1) AAS
お題：英字の羅列された文字列が与えられる。この文字列を分析して数字列を出力せよ。数字の表記ルールは、その文字の両隣の文字がASCIIコードにおける奇数だったら1、そうでなければ0.

206(23): デフォルトの名無しさん [] 2024/02/02(金) 06:41:15.23 ID:CC6U77IS(1) AAS
お題
入力データをグループ分けして出力せよ

入力データの、= の左右は同じグループである。
出力する順番は、入力データの出現順とする

UnionFind を使えば良いかも

入力データ
["a1=a2", "b1=b2", "b3=b2", "c1=c2", "e1=e2",
"a3=a4", "c3=c4", "e1=e3", "a2=a4", "c3=c1",
"b3=a4", "c2=d1", "a4=a5", "d2=c1", "b4=b3", "d3=c3"]

出力
[["a1", "a2", "b1", "b2", "b3", "a3", "a4", "a5", "b4"],
["c1", "c2", "c3", "c4", "d1", "d2", "d3"],
["e1", "e2", "e3"]]

Ruby で、UnionFind を自作してみた。
下はユニットテストです

外部ﾘﾝｸ:paiza.io
外部ﾘﾝｸ:paiza.io

221(1): 211 [sage] 2024/02/04(日) 23:55:45.21 ID:ytAuzkvH(1) AAS
>>206 ruby
外部ﾘﾝｸ:ideone.com
・>>211から若干のアレンジ
・同一グループの収集にSortedSetを使用

468(2): デフォルトの名無しさん [sage] 2025/01/03(金) 17:52:02.97 ID:aGLRGnDr(3/3) AAS
>>464 lisp (chatgptに教えてもらった)
外部ﾘﾝｸ:ideone.com
外部ﾘﾝｸ:chatgpt.com

485(20): デフォルトの名無しさん [] 2025/01/22(水) 21:35:12.82 ID:JtEnwxKE(1) AAS
お題

文字列と長さを入力として受け取り
デカルト積のリストを出力してください

入力：ABC 1
出力：[A, B, C]

入力：ABC 2
出力：[AA, AB, AC, BA, BB, BC, CA, CB, CC]

入力：ABC 3
出力：[AAA, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC, BAA, BAB, BAC, BBA, BBB, BBC, BCA, BCB, BCC, CAA, CAB, CAC, CBA, CBB, CBC, CCA, CCB, CCC]

772(1): デフォルトの名無しさん [sage] 2025/07/25(金) 20:46:23.28 ID:dyl0C+2U(1) AAS
>>771
例がおかしい
わかりやすい最後の例で示すと

入力： 0 1 0 1 0 1 0 1
出力： 0 4 1 5 2 6 3 7　間違い
出力： 0 2 4 6 1 3 5 7　正解

安定ソートなので同値は順序を保ってこうなる

814(1): デフォルトの名無しさん [sage] 2025/08/22(金) 06:55:21.34 ID:qlaiAqZd(1/2) AAS
>>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()
}