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 

[MP]

Code: [Select]

def reverseNths (nths, lst):
    result=list(lst[::]) ; nths=list(nths) ; nths.sort()
    lst2=list(lst[i] for i in nths) ; lst2.reverse()
    for i,j in enumerate(nths): result[j]=lst2[i]
    return result

Code: [Select]

reverseNths((1,4,5), (0,1,2,3,4,5,6,7))

>>> [0, 5, 2, 3, 4, 1, 6, 7]

Code: [Select]

reverseNths((5,1,4), (0,1,2,3,4,5,6,7))

>>> [0, 5, 2, 3, 4, 1, 6, 7]
Added bonus:

Code: [Select]

reverseNths((5,1,4),'abcdefg')

>>> ['a', 'f', 'c', 'd', 'e', 'b', 'g']

[Lee Mac]

Nice Python(?) solution Michael!

Your approach sparked an idea:

Code: [Select]

(defun ReverseItems ( idx lst / arr )
  (setq arr
    (vlax-safearray-fill
      (vlax-make-safearray vlax-vbVariant (cons 0 (1- (length lst)))) lst
    )
  )
  (mapcar
    (function
      (lambda ( a b )
        (vlax-safearray-put-element arr a b)
      )
    )
    (setq idx (vl-sort idx '<)) (mapcar '(lambda ( x ) (nth x lst)) (reverse idx))
  )
  (mapcar 'vlax-variant-value (vlax-safearray->list arr))
)
[ Edited to sort index list ]

[LE3]

geez... can't compete with those very compacted linear coding stylish's - unless i make a class with a set of functions, and exposed them in that similiar style... but dang' to much work for a simple challenge.

need to find time to learn another new language...  

[MP]

Nice Python(?) solution Michael!

ummm, yeah, guess I should have spec'd what language it was

Your approach sparked an idea:

Code: [Select]

(defun ReverseItems ( idx lst / arr )
  (setq arr
    (vlax-safearray-fill
      (vlax-make-safearray vlax-vbVariant (cons 0 (1- (length lst)))) lst
    )
  )
  (mapcar
    (function
      (lambda ( a b )
        (vlax-safearray-put-element arr a b)
      )
    )
    idx (mapcar '(lambda ( x ) (nth x lst)) (reverse idx))
  )
  (mapcar 'vlax-variant-value (vlax-safearray->list arr))
)

cool, ain't programming fun?

[Lee Mac]

Nice Python(?) solution Michael!

ummm, yeah, guess I should have spec'd what language it was

Well, I was pretty sure it was Python, but not 100% 

ain't programming fun?

I'm pretty much addicted, yeah

[LE3]

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

Here it is a release version of my arx function (for acad 2010-2011)

Command:
***Usage: ReverseByIndices(<list of strings> <list of integers - indices>) ***

Some testings:

(setq l (reversebyindices (list "A" "B" "C" "D" "E" "F" "G" "H") (list 1 3 4)))
;;("A" "E" "C" "D" "B" "F" "G" "H")

;;(A B C D E F G H)  -->  (A E C D B F G H)

;;0 2 5 6
(setq l (reversebyindices (list "A" "B" "C" "D" "E" "F" "G" "H") (list 0 2 5 6)))
;;("G" "B" "F" "D" "E" "C" "A" "H")

;;(A B C D E F G H)  -->  (G B F D E C A H)

(setq l (reversebyindices (list "A" "B" "C" "D" "E" "F" "G" "H") (list 1 3)))
 0 1 2 3
(A B C D E F G H)
("A" "D" "C" "B" "E" "F" "G" "H")

(setq l (reversebyindices (list "A" "B" "C" "D" "E" "F" "G" "H") (list 1)))
("A" "B" "C" "D" "E" "F" "G" "H")

(setq l (reversebyindices (list "A" "B" "C" "D" "E" "F" "G" "H") (list 1 1 1 3 3 3 4 4 4)))

(setq l (reversebyindices (list "A" "B" "C" "D" "E" "F" "G" "H") (list 1 2 3 4 5 6 7 8 9 10 11 12 13)))

(setq l (reversebyindices (list "A" "B" "C" "D" "E" "F" "G" "H") (list -1 -2)))

[pkohut]

If I understand correctly what the outputs should be...C++ version

Code: [Select]

#include <iostream>
#include <vector>
using namespace std;

void ReverseIndice(vector<int> indices, vector<char> & lst)
{
    sort(indices.begin(), indices.end()); // edit: added this to get same results as Lee's func
    vector<int>::const_iterator it = indices.begin();
    vector<int>::const_iterator rit = indices.end() - 1;
    
    for(; it != indices.begin() + indices.size() / 2; ++it, --rit)
        swap(lst.at(*it), lst.at(*rit));
}

#define ELEMENTS(x) sizeof(x) / sizeof(x[0])

int main(int argc, char *argv[])
{
    char items_array[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
//  int indices_array[] = {1, 3, 4};
    int indices_array[] = {0, 2, 5, 6};
//  int indices_array[] = {0, 5, 1 ,2};
    
    // make vectors from arrays
    vector<char> lst(items_array, &items_array[ELEMENTS(items_array)]);
    vector<int> indices(indices_array, &indices_array[ELEMENTS(indices_array)]);

    ReverseIndice(indices, lst);

    // output list
    for(int i = 0; i < lst.size(); i++)
        cout << lst.at(i) << " ";

    return 0;
}


edit: with the sort(indices.begin(), indices.end()); (corrected output)
{1, 2, 3}     {A, B, C, D, E, F, G, H} => A E C D B F G H
{0, 2, 5, 6} {A, B, C, D, E, F, G, H} => G B F D E C A H
{0, 5, 1, 2} {A, B, C, D, E, F, G, H} => F C B D E A G H
witout sort function:
{0, 5, 1, 2} {A, B, C, D, E, F, G, H} => C F A D E B G H

[pkohut]

C++ version converted to Python (note pythonic swap (no temp var needed))

Code: [Select]

def revNths(nths, lst):
result = list(lst); nths = list(nths); nths.sort()
i = 0; j = len(nths) - 1
while(i < len(nths) / 2):
result[nths[i]], result[nths[j]] = result[nths[j]], result[nths[i]]
i += 1; j -= 1;
return result


>>> revNths((1, 3, 4), "abcdefgh")
['a', 'e', 'c', 'd', 'b', 'f', 'g', 'h']
>>> revNths((0, 2, 5, 6), "abcdefgh")
['g', 'b', 'f', 'd', 'e', 'c', 'a', 'h']
>>> revNths((0, 5, 1, 2), "abcdefgh")
['f', 'c', 'b', 'd', 'e', 'a', 'g', 'h']
>>> revNths((0, 5, 1, 2, 3), "abcdefgh")
['f', 'd', 'c', 'b', 'e', 'a', 'g', 'h']

[Lee Mac]

Nice idea Paul to only perform half the iterations!

[LE3]

Code: [Select]

char items[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
const int indices[] = { 1, 3, 4, };
std::vector<char, std::allocator<char>> v (items, items + sizeof items / sizeof *items);
std::vector<char, std::allocator<char>> v2;
std::vector<int, std::allocator<int>> idxs (indices, indices + sizeof indices / sizeof *indices);
std::reverse(idxs.begin(), idxs.end());
for (int i = 0; i < idxs.size(); i++)
v2.push_back(v.at(idxs.at(i)));
std::reverse(idxs.begin(), idxs.end());
for (int i = 0; i < idxs.size(); i++)
v.at(idxs.at(i)) = v2.at(i);
for (int i = 0; i < v.size(); i++)
acutPrintf(_T("%s "), AcString(v.at(i)).kACharPtr());


[pkohut]

Code: [Select]

<<snip>>


Not bad, need to sort indices though. This is based off yours, removes the reverse calls and clean up the code a bit and add some white space.

Code: [Select]

int main(int argc, char *argv[])
{
    char _items[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
    int _indices[] = { 0, 5, 1, 2, };
    vector<char> items(_items, &_items[ELEMENTS(_items)]);
    vector<int> indices(_indices, &_indices[ELEMENTS(_indices)]);
    vector<char> pickedItems;

    sort(indices.begin(), indices.end());
    for(vector<int>::reverse_iterator rit = indices.rbegin(); rit != indices.rend(); ++rit)
        pickedItems.push_back(items.at(*rit));

    for(int i = 0; i < pickedItems.size(); ++i)
        items.at(indices.at(i)) = pickedItems.at(i);

    for (int i = 0; i < items.size(); ++i)
        cout << items[i] << " ";
    cout << endl;

    system("pause");
    return 0;
}


[pkohut]

Here's a a final more "C" like version, much cleaner and easier to read.

Code: [Select]

int main(int argc, char *argv[])
{
    char items[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
    int indices[] = { 0, 2, 5, 6, };
    size_t nIndices = ELEMENTS(indices);
    char * pPickedItems = (char *) alloca(sizeof(char) * nIndices);

    sort(indices, &indices[nIndices]);
    for(int i = nIndices - 1, j = 0; i >= 0; --i, ++j)
        pPickedItems[j] = items[indices[i]];

    for(int i = 0; i < nIndices; ++i)
        items[indices[i]] = pPickedItems[i];

    for (int i = 0; i < ELEMENTS(items); ++i)
            cout << items[i] << " ";
    cout << endl;

    system("pause");
    return 0;
}


[LE3]

Not bad, need to sort indices though. This is based off yours, removes the reverse calls and clean up the code a bit and add some white space.

Oops, forgot that part...



Now it looks good

[LE3]

This looks good, Paul

Here's a a final more "C" like version, much cleaner and easier to read.

Code: [Select]

int main(int argc, char *argv[])
{
    char items[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
    int indices[] = { 0, 2, 5, 6, };
    size_t nIndices = ELEMENTS(indices);
    char * pPickedItems = (char *) alloca(sizeof(char) * nIndices);

    sort(indices, &indices[nIndices]);
    for(int i = nIndices - 1, j = 0; i >= 0; --i, ++j)
        pPickedItems[j] = items[indices[i]];

    for(int i = 0; i < nIndices; ++i)
        items[indices[i]] = pPickedItems[i];

    for (int i = 0; i < ELEMENTS(items); ++i)
            cout << items[i] << " ";
    cout << endl;

    system("pause");
    return 0;
}