Лучший способ найти все уникальные комбинации элементов массива? - PullRequest
Новая
       13

Лучший способ найти все уникальные комбинации элементов массива?

0 голосов
/ 27 февраля 2020

У меня есть массив некоторых определенных целых, и я хочу найти все уникальные комбинации (путем добавления) этих целых. Я уверен, что есть способ сделать это функционально; Я пытаюсь избежать итеративного способа добавления циклов внутри циклов for. Я использую Rust в этом случае, но этот вопрос, в общем, "функциональное программирование, как?" брать.

Моя первая мысль: мне нужно просто сжать каждую запись в v с каждой другой записью, сократить их путем добавления к одному элементу и отфильтровать дубликаты. Это O (| v | ^ 2), который плохо себя чувствует, а это означает, что я, вероятно, упускаю что-то довольно очевидное для функциональных одаренных детей. Кроме того, я даже не уверен, как это сделать, я, вероятно, использовал бы для l oop для создания моего нового массивного массива.

Мой первый проход: обратите внимание, что v содержит все числа, которые я забота о. 

let mut massive_arr = Vec::new();
for &elem in v.iter(){
  for &elem2 in v.iter(){
  massive_arr.push((elem,elem2));
  }
}
let mut single_massive = Vec::new();
for &tuple in massive_arr.iter(){
  single_massive.push(tuple.0 + tuple.1);
}
single_massive.dedup();
let summand: usize = single_massive.iter().sum();                                                println!("The sum of all that junk is {:?}", summand);```

Помогите мне крестить мои испорченные итерации в чистом свете функционального программирования.

отредактировано: Я приводил пример прежде, как я все еще был выяснение реализации, которая действительно работала, и вопрос был скорее в том, как мне сделать этот лучший вопрос. То, что выше, сейчас действительно работает (но все еще ужасно!).

Ответы [ 2 ]

1 голос
/ 28 февраля 2020

Улучшая ответ @ phimuemue, вы можете избежать очевидных дубликатов, таких как: 

v.iter()
 .enumerate()
 .flat_map (|(i, a)| v[i+1..].iter().map (move |b| a+b))
 .unique()    // May not be needed or what you really want, see note below
 .sum()

Детская площадка

Обратите внимание, что это может не дать вам ответ Вы действительно хотите, если несколько пар чисел имеют одинаковую сумму. Например, учитывая vec![1, 2, 3, 4] в качестве входных данных, вы ожидаете:

  • (1+2) + (1+3) + (1+4) + (2+3) + (2+4) + (3+4) = 30
  • или 3 + 4 + 5 + 6 + 7 = 25, поскольку 1+4 == 2+3 == 5 считается только один раз?
1 голос
/ 27 февраля 2020

Вы можете использовать itertools (у меня нет компилятора под рукой, но вы, вероятно, поняли идею): 

use itertools::Itertools;

iproduct!(v.iter(), v.iter())     // construct all pairs
    .map(|tuple| tuple.0+tuple.1) // sum each pair
    .unique()                     // de-duplicate (uses a HashMap internally)
    .sum()                        // sum up

Все это все еще O (n ^ 2), который - как Насколько я вижу - асимптотически оптимально, потому что могут понадобиться все пары чисел.

Чтобы избежать очевидных дубликатов, вы можете использовать tuple_combinations: 

v.iter()
    .tuple_combinations()
    .map(|(a, b)| a+b)
    .unique()
    .sum()
...