プログラミングのお題スレ Part22 (859ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
771(22): デフォルトの名無しさん [sage] 07/25(金)12:30 ID:CjDQVF2B(1)
【問題】
整数のリストが与えられたとき、そのリストを昇順に安定ソートした時の各要素のインデクス（0開始）を対応させたリストを作成せよ
【例】
入力： 1 100 10 10000 1000
出力： 0 2 1 4 3
入力： 3 1 4 1 5 9 2
出力： 3 0 4 1 5 6 2
入力： 0 1 0 1 0 1 0 1
出力： 0 4 1 5 2 6 3 7
実際に必要になって実装したけどスマートな方法があったら知りたい
772(1): デフォルトの名無しさん [sage] 07/25(金)20:46 ID:dyl0C+2U(1)
>>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 正解
安定ソートなので同値は順序を保ってこうなる
773: デフォルトの名無しさん [sage] 07/25(金)21:30 ID:Z69qH9vG(1)
>>771 C++ 特にひねりは無い
https://ideone.com/mTHn46
775: デフォルトの名無しさん [] 07/26(土)15:08 ID:T78ZrTu7(1/2)
>>771
SQL
select
row_number() over(order by arrayValue, arrayIndex) - 1
from
arrayTable
order by
arrayIndex
776(1): デフォルトの名無しさん [] 07/26(土)19:25 ID:T78ZrTu7(2/2)
>>771
Java 24
https://text.is/4Z27R
777(1): デフォルトの名無しさん [sage] 07/27(日)10:09 ID:vFJ24xnO(1/3)
>>771 ocaml
https://ideone.com/E7eFPC
>>771 octave
https://ideone.com/KkHu9S
>>771 ruby
https://ideone.com/pPIxcE
778: デフォルトの名無しさん [sage] 07/27(日)17:05 ID:vFJ24xnO(2/3)
>>771 c
https://ideone.com/6Wn3eD
779: デフォルトの名無しさん [sage] 07/27(日)17:08 ID:vFJ24xnO(3/3)
>>771 ruby 2.6以降？
sorti = ->a {a.map.with_index.sort.map &:last}
f = sorti << sorti
g = method(:p) << f
780: デフォルトの名無しさん [] 07/27(日)20:19 ID:uFbo+/2v(1)
>>771
R
https://ideone.com/ctaQC5
統計用言語だけあってライブラリ関数rankを呼び出すだけ。ties.method = "min"を指定すれば
同値を同順位（例えば2番目の例では出力が3 0 4 0 5 6 2となる）にもできる。
781: デフォルトの名無しさん [sage] 07/27(日)21:43 ID:w39E9j9Q(1)
>>771
Rust
既に色々と出ているため別の観点からのコード
一時作業メモリ最小 ＆ ソートは1回 ＆ ジェネリック
fn f<T: std::cmp::Ord>(input: &[T]) -> Vec<usize> {
let len = input.len();
// ポジションのリスト [0, 1, 2, 3, ... , len-1] を作成
let mut pos_list: Vec<usize> = (0..len).collect();
// inputを利用してそのポジションだけをソート
pos_list.sort_by_key(|&pos| &input[pos]);
// 返すべきランクのリスト
let mut rank_list: Vec<usize> = vec![0; len];
// ポジション⇔ランクは逆写像なのでソートは不要
(0..len).for_each(|rank| rank_list[pos_list[rank]] = rank);
rank_list
}
fn main() {
assert_eq!(f(&[1, 100, 10, 10000, 1000]), [0, 2, 1, 4, 3]);
assert_eq!(f(&[3, 1, 4, 1, 5, 9, 2]), [3, 0, 4, 1, 5, 6, 2]);
assert_eq!(f(&[0, 1, 0, 1, 0, 1, 0, 1]), [0, 4, 1, 5, 2, 6, 3, 7]);
}
782: 777 [sage] 07/27(日)22:54 ID:YfUjoiLt(1)
>>771 octave ソート一回
https://ideone.com/dTRKBs
>>771 ruby 2.5 ソート一回
https://ideone.com/akDhpS
783: 警備員[Lv.11] [] 07/28(月)23:30 ID:uO5vEij8(1)
>>771
>>776をKotlinに変換してKotlinらしくなるように色々省略しただけのもの。
やはり最初からラムダとか考慮されている言語だと色々省略できて分り易くなるね。
https://paiza.io/projects/0Dhknk4mUHrMqtuwzCDAxQ
784: デフォルトの名無しさん [sage] 07/29(火)00:12 ID:9AXsNEm+(1)
>>771
Rust
https://ideone.com/jYX2ws
バイナリヒープ使うとソート過程で直接リスト作れるけどコード量増えるしヒープソート遅いから実用性は微妙か
C言語ならありかもしれない
785(1): デフォルトの名無しさん [sage] 07/30(水)21:50 ID:Ug40aZKP(1)
>>771 java
https://ideone.com/Z8Q9Dk
788: 785 [sage] 07/31(木)21:15 ID:R3hgrYP8(1)
>>771 java compose乱用
https://ideone.com/TBTZgj
789(1): デフォルトの名無しさん [sage] 08/03(日)22:00 ID:1jv9m6G7(1)
>>771
java >>786を修正。javaが古いねぇ。
https://ideone.com/Z3jS0P
790(1): デフォルトの名無しさん [sage] 08/04(月)22:42 ID:A9zbJQ8U(1/2)
>>771
java >>789を修正。何度もすいませんね。classをメソッド内に移動。
https://ideone.com/BV5FXe
791: デフォルトの名無しさん [sage] 08/04(月)23:09 ID:A9zbJQ8U(2/2)
>>771
java >>790修正。classだったらメソッドの引数がみえるので修正。recordではできない。
https://ideone.com/r6T4Zf
793: デフォルトの名無しさん [] 08/06(水)17:17 ID:qE4NV2ND(1)
>>771
JavaScript
https://paiza.io/projects/xtvAB2LXpLg0XOjzBHfl2w
795: デフォルトの名無しさん [sage] 08/10(日)23:18 ID:FODtZCg5(1)
>>771 scala
https://ideone.com/iycaKk
>>771 swift
https://ideone.com/de2iOi
796: デフォルトの名無しさん [sage] 08/11(月)20:38 ID:frWpQyFA(1)
>>771 dart 2.3
https://ideone.com/XLI2nC
・拡張メソッドはDart2.7から
・ideone現状はDart (dart 2.3.0)
797: デフォルトの名無しさん [] 08/12(火)21:05 ID:uRUBTkGF(1/2)
>>771
PowerShell 6以降
function rank($a)
{
$n = $a.length
$r = [int[]]::new($n)
if ($n) {0..($n - 1) | sort-object -stable {$a[$_]} |% {$i = 0} {$r[$_] = $i++}}
$r
}
function PrintArray($a)
{
if ($a.length -le 1) {return $a}
"[$(($a |% {PrintArray $_}) -join ", ")]"
}
$q =
(1, 100, 10, 10000, 1000),
(3, 1, 4, 1, 5, 9, 2),
(0, 1, 0, 1, 0, 1, 0, 1),
@(),
1,
((1, 1), (1, 1), (1, 0, 1), (1, 0))
$q |% {
"入力: $(PrintArray $_)"
"出力: $(PrintArray (rank $_))"
""
}
810: デフォルトの名無しさん [sage] 08/19(火)21:28 ID:ahVErwF8(1)
>>771 scheme (chicken 4.13)
https://ideone.com/RREeGy
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.053s