Topic: -={ Challenge }=- Reverse Items

[Lee Mac]

When recently updating my TabSort program here, I was looking at the old subfunction I used to reverse specific items in a list and thought to myself that it would be interesting to see other ways to approach the same problem.

So, I pose this as as challenge to the community 

The Challenge:

To construct a function to reverse specific items within a list, given a list of indexes - I suppose this is best illustrated by an example:

Code: [Select]

(setq lst '(A B C D E F G H))

Code: [Select]

(ReverseItems '(1 3 4) lst)
(A [color=red]B[/color] C [color=red]D[/color] [color=red]E[/color] F G H)  -->  (A [color=red]E[/color] C [color=red]D[/color] [color=red]B[/color] F G H)

Code: [Select]

(ReverseItems '(0 2 5 6) lst)
([color=red]A[/color] B [color=red]C[/color] D E [color=red]F[/color] [color=red]G[/color] H)  -->  ([color=red]G[/color] B [color=red]F[/color] D E [color=red]C[/color] [color=red]A[/color] H)
Here is the method I used in my TabSort program:

Code: [Select]

(defun ReverseItems ( idx lst )
  (
    (lambda ( i l )
      (mapcar
        (function
          (lambda ( x )
            (if (member (setq i (1+ i)) idx)
              (setq x (nth (car l) lst) l (cdr l))
            )
            x
          )
        )
        lst
      )
    )
    -1 (reverse (vl-sort idx '<))
  )
)
Have fun!

Lee

[CAB]

Modified one of my old routines.

Code: [Select]

(defun SwapItms (itms lst / idx)
  (while (and (setq i1 (car itms)) (setq i2 (last itms)))
    (setq idx -1 itms (cdr itms) itms (reverse (cdr (reverse itms))))
    (setq lst
    (mapcar '(lambda (x)
               (setq idx (1+ idx))
               (cond
                 ((= idx i2) (nth i1 lst))
                 ((= idx i1) (nth i2 lst))
                 (x)
               )
             )
      lst
    )
          )
  )
    lst
)

[Lee Mac]

Nice idea Alan! I like the way you shorten the itms list from both sides 

[CAB]

Thanks Lee, wish there was a way to do that without the double reverse.

[gile]

Hi,

Another way

Code: [Select]

(defun ReverseItems (idx lst / foo)
  (defun foo (idx lst itm)
    (cond
      ((or (null idx) (null lst)) lst)
      ((zerop (car idx))
       (cons (car itm) (foo (cdr (mapcar '1- idx)) (cdr lst) (cdr itm)))
      )
      ((cons (car lst) (foo (mapcar '1- idx) (cdr lst) itm)))
    )
  )
  (foo idx lst (reverse (mapcar '(lambda (x) (nth x lst)) idx)))
)

[CAB]

Just goofing around with odd pointers.

Code: [Select]

_$ (ReverseItems '(0 5 1 2) '("a" "b" "c" "d" "e" "f" "g" "h"))
("f" "c" "b" "d" "e" "a" "g" "h")
_$ (SwapItms '(0 5 1 2) '("a" "b" "c" "d" "e" "f" "g" "h"))
("c" "f" "a" "d" "e" "b" "g" "h")
_$ (gileReverseItems '(0 5 1 2) '("a" "b" "c" "d" "e" "f" "g" "h"))
("c" "b" "c" "d" "e" "b" "g" "h")

Code: [Select]

_$ (SwapItms '(0 1 5 2) '("a" "b" "c" "d" "e" "f" "g" "h"))
("c" "f" "a" "d" "e" "b" "g" "h")
_$ (ReverseItems '(0 1 5 2) '("a" "b" "c" "d" "e" "f" "g" "h"))
("f" "c" "b" "d" "e" "a" "g" "h")
_$ (gileReverseItems '(0 1 5 2) '("a" "b" "c" "d" "e" "f" "g" "h"))
("c" "f" "c" "d" "e" "b" "g" "h")

[Lee Mac]

Another way...

I should imagine this would prevail with long lists in which the items to be reversed are all near the start of the list - your method is good in that the whole list needn't be iterated. 

[Lee Mac]

Just goofing around with odd pointers.

Interesting results! I should imagine the variation occurs as some codes do not account for the index list not being in numerical order 

[CAB]

Yes but this is in order:
'(0 1 5 2)

PS OK I see what you mean. This would be an odd case.

[LE3]

Here it is a quick one, that just wrote:

Code: [Select]

void ReverseByIndices(std::vector<CString> &items, std::vector<int> positions)
{
std::vector<CString>::iterator it;
std::vector<int>::iterator itPos;
std::vector<CString> indices;
itPos = positions.begin();
while (itPos != positions.end())
{
indices.push_back(items[*itPos]);
itPos++;
}
std::reverse(indices.begin(), indices.end());
for (int i = 0; i < indices.size(); i++)
{
it = std::find(items.begin(), items.end(), indices[i]);
if (it != items.end()) items.erase(it);
}
for (int i = 0; i < indices.size(); i++)
{
items.insert(items.begin() + positions[i], indices[i]);
}
indices.clear();
positions.clear();
}

And to test the above function it returns the same output using Lee's list's samples:

Code: [Select]

std::vector<CString>::iterator it;
std::vector<CString> items;
std::vector<int> positions;
items.push_back("A");
items.push_back("B");
items.push_back("C");
items.push_back("D");
items.push_back("E");
items.push_back("F");
items.push_back("G");
items.push_back("H");
//positions.push_back(1);
//positions.push_back(3);
//positions.push_back(4);

positions.push_back(0);
positions.push_back(2);
positions.push_back(5);
positions.push_back(6);

acutPrintf(_T("\nOriginal: "));
for (int i = 0; i < items.size(); i++)
{
acutPrintf(_T("%s "), items[i]);
}

ReverseByIndices(items, positions);

acutPrintf(_T("\nAfter: "));
for (int i = 0; i < items.size(); i++)
{
acutPrintf(_T("%s "), items[i]);
}
items.clear();


[gile]

Trying the F# route:

Code: [Select]

let reverseItems idx lst =
    let xdi = idx |> List.rev
    lst |> List.permute (fun x ->
                            match idx |> List.tryFindIndex(fun n -> n = x) with
                            | Some(i) -> xdi.[i]
                            | None -> x)

> reverseItems [1; 3; 4] lst;;
val it : string list = ["a"; "e"; "c"; "d"; "b"; "f"; "g"; "h"]
> reverseItems [0; 2; 5; 6] lst;;
val it : string list = ["g"; "b"; "f"; "d"; "e"; "c"; "a"; "h"]

[Lee Mac]

Trying the F# route...

Wow - F# is pretty concise!

[Lee Mac]

Was thinking something like this to test them, but not sure how to test the non-LISP solutions 

Code: [Select]

(defun test ( / rand l len idx )

  ;; SMadsen
  (defun rand ( minN maxN / _rand )
   
    (defun _rand ( / modulus multiplier increment )     
      (if (not seed) (setq seed (getvar 'DATE)))

      (setq modulus 4294967296.0 multiplier 1664525 increment 1
            seed    (rem (+ (* multiplier seed) increment) modulus)
      )
      (/ seed modulus)
    )
    (fix (+ minN (* (_rand) (- (1+ maxN) minN))))
  )

  (setq l '(A B C D E F G H I J))

  (repeat 6 (setq l (append l l)))

  (setq len (length l)
        idx (repeat (/ len 4) (setq idx (cons (rand 0 (1- len)) idx)))
  )
  (princ (strcat "\n--> List Length: " (itoa len) ", Reversing " (itoa (length idx)) " items.\n"))

  (Benchmark
   '(
      (gc:ReverseItems idx l)
      (CAB:SwapItms idx l)
      (LM:ReverseItems idx l)
    )
  )

  (princ)
)
Reverses a random quarter of the list - thanks to Stig for the Random-in-Range function.

[gile]

Wow - F# is pretty concise!

Yes it is !
And it provides many methods to deal with collections, as here, the 'permute' method from the List module.

A LISP way closed to the F# one.

Code: [Select]

(defun subst-i (new ind lst)
  (if (or (zerop ind) (null lst))
    (cons new (cdr lst))
    (cons (car lst) (subst-i new (1- ind) (cdr lst)))
  )
)

(defun reverseItems (idx lst)
  (last
    ((lambda (l)
       (mapcar '(lambda (i1 i2)
  (setq lst (subst-i (nth i2 l) i1 lst))
)
       idx
       (reverse idx)
       )
     )
      lst
    )
  )
)

[Lee Mac]

Wow - F# is pretty concise!

Yes it is !
And it provides many methods to deal with collections, as here, the 'permute' method from the List module.

How does it compare in speed with other languages? I would think LISP is quite low in the list, but is F# faster than say, C#?

A LISP way closed to the F# one.

Another for me to study