F # - як групувати попередній, цей і наступні елементи в круговій послідовності

У F # Як найкраще перетворити кінцеву послідовність, подібну seq [0; 1; 2; 3; 4] у послідовність кортежів, як seq [4,0,1; 0,1,2; 1,2,3; 2,3,4; 3,4,0] ?

Addition: My Seq represents circular data. In this case the vertices of a closed polyline. I need the neighboring elements to compute the angle of each corner.

4

7 Відповіді

Ось просте рішення, яке використовує лише послідовності. Зверніть увагу, що якщо вхід і вихід завжди будуть списком, є трохи більш складне, але більш швидке рішення, яке використовує лише списки і проходить лише один раз.

// Example usage: neighbors [0..4]
let neighbors input =
    let inputLength = Seq.length input
    input
   //The sequence needs to be looped three times;
   //the first and last time handle the previous value for the first
   //element in the input sequence and the next value for the last
   //element in the input sequence, respectively.
    |> Seq.replicate 3
   //Start at the previous element of the first element in the input sequence.
    |> Seq.skip (inputLength - 1)
   //Take the same number of elements as the tuple.
    |> Seq.windowed 3
   //Only keep the same number of elements as the original sequence.
    |> Seq.take inputLength
   //Convert the arrays to tuples
    |> Seq.map (fun values ->
        values.[0], values.[1], values.[2])
   //Return the result as a list of tuples.
    |> Seq.toList
8
додано
чи багато точок з використанням Seq, якщо перше, що ви робите, це виклик Seq.length? також Seq.replicate розширення?
додано Автор jk., джерело
@bytebuster Так, це правильно; але враховуючи вхідний вибір, це може не мати значення. Якщо можна мати повторювані значення, то краще реалізувати згадане рішення на основі списку.
додано Автор Jack P., джерело
@bytebuster Подумавши про це ще вранці, я подумав про кращий спосіб вирішити цю проблему, яка не вимагає Seq.distinct , а також не має жодних проблем з дублюючими значеннями.
додано Автор Jack P., джерело
@jk Єдина причина, за якою я б використовував Seq тут, щоб зберегти цю функцію загальною (в тому, що вона може працювати з послідовностями, списком, масивами і т.д.). Проте, як я вже згадував у відповіді, якщо ви знаєте, що вхід завжди буде більш специфічним типом колекції, наприклад список або масив , існують більш швидкі способи реалізації цієї функції . Seq.replicate - це функція, що надається в ExtCore .
додано Автор Jack P., джерело
let windowedEx n (s: seq<_>) =
  let r = ResizeArray(s)
  if r.Count > 1 then
    let last = r.[r.Count-1]
    r.Add(r.[0])
    r.Insert(0, last)
  Seq.windowed n r
3
додано

Тут є кілька хороших відповідей, ось ще один. Для мене це виглядає найбільш читабельним, має складність O (n) , а також зберігає певну помилку:

// Returns the last element of a sequence.
// Fails on empty sequence
let last xs =
    let len = Seq.length xs - 1
    if len < 0 then failwith "Sequence must be non-empty"
    xs
    |> Seq.skip len
    |> Seq.head

// Converts an array into a tuple
let toTuple = function
    | [|a; b; c|] -> (a, b, c)
    | _ -> failwith "Must be an array with exactly 3 elements"

let windowedBy3 xs =
    seq {
        yield last xs;
        yield! xs;
        yield Seq.head xs
    }
    |> Seq.windowed 3
    |> Seq.map toTuple

// Usage
Seq.init 5 id
|> windowedBy3
|> Seq.iter (printf "%A; ")
3
додано

Це дає правильну відповідь, хоча елемент, який у вас є вперше, приходить останнім, але це не проблема, ви можете знайти кут для кожного з трьох пунктів.

let cycle s =
    Seq.append s (Seq.take 2 s)//append the first two elements to the and
    |> Seq.windowed 3          //create windows of 3
    |> Seq.map (fun a -> (a.[0], a.[1], a.[2]))//create tuples


// test
[0;1;2;3;4] |> cycle

// returns:
>
  val it : seq =
  seq [(0, 1, 2); (1, 2, 3); (2, 3, 4); (3, 4, 0); ...]
3
додано

Якщо ви не вимагаєте лінь, використання проміжного масиву може бути більш ефективним, наприклад,

// get items (i-1, i, i+1) from arr; wrap around at the boundaries
let adj3 i (arr: 'a[]) =
   //modulo operator that works correctly
    let inline (%%) x y = ((x % y) + y) % y
    let len = arr.Length
    arr.[(i - 1) %% len], arr.[i], arr.[(i + 1) %% len]

let windowed3 s = seq { 
    let sarr = s |> Seq.toArray    
    for i = 0 to sarr.Length do 
        yield adj3 i sarr }

Складність часу в O ( n ).

3
додано
Ні, я так не думаю. Отримання останнього елемента послідовності вимагає перерахування/примусового виконання всієї послідовності принаймні один раз (що є Seq.toArray , а також Seq.skip len , ResizeArray <_> (s) і т.д.).
додано Автор Frank, джерело
Мені подобається ваш оператор по модулю. Чи може SEQ ще ледачий, якщо мені потрібно знати останній елемент з самого початку?
додано Автор Goswin, джерело

Я б зробив це так:

let neighbors xs =
  match Array.ofSeq xs with
  | [||] -> [||]
  | [|x|] -> [|x, x, x|]
  | xs ->
      let n = xs.Length
      [|yield xs.[n-1], xs.[0], xs.[1]
        for i=1 to n-2 do
          yield xs.[i-1], xs.[i], xs.[i+1]
        yield xs.[n-2], xs.[n-1], xs.[0]|]

Порівняння зазвичай набагато швидше, ніж арифметичність по модулю. Щоб зробити це швидше, попередньо виділіть масив і заповніть елементи замість вираження послідовності.

2
додано

Як буде виглядати загальне рішення для Seq.circularWindowed ? Враховуючи розмір вікна n , потрібно спочатку спожити перші елементи n - 1 , зберігаючи при цьому решту. У випадку, якщо в джерелі не більше ніж n - 1 елементів, він створює порожню послідовність.

Отже, це ResizeArray для кешу та послідовного виразу для зшивання всіх цих елементів.

module Seq =
    let circularWindowed n (xs : seq<_>) =
        let en = xs.GetEnumerator()
        let ra = ResizeArray()
        while ra.Count < n - 1 && en.MoveNext() do
            ra.Add en.Current
        seq{
            if en.MoveNext() then 
                yield! ra
                yield en.Current
                while en.MoveNext() do
                    yield en.Current
                yield! ra }
        |> Seq.windowed n

seq [0; 1; 2; 3; 4]
|> Seq.circularWindowed 3
|> Seq.toList
// val it : int [] list =
//   [[|0; 1; 2|]; [|1; 2; 3|]; [|2; 3; 4|]; [|3; 4; 0|]; [|4; 0; 1|]]
1
додано