TheSwamp
Code Red => AutoLISP (Vanilla / Visual) => Topic started by: Lee Mac on December 11, 2010, 03:12:42 PM
-
When recently updating my TabSort program here (http://lee-mac.com/tabsort.html), 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:
(setq lst '(A B C D E F G H))
(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)
(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:
(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
-
Modified one of my old routines. 8-)
(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
)
-
Nice idea Alan! I like the way you shorten the itms list from both sides :-)
-
Thanks Lee, wish there was a way to do that without the double reverse.
-
Hi,
Another way
(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)))
)
-
Just goofing around with odd pointers.
_$ (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")
_$ (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")
-
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. :-)
-
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 :-)
-
Yes but this is in order:
'(0 1 5 2)
PS OK I see what you mean. This would be an odd case.
-
Here it is a quick one, that just wrote:
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:
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();
-
Trying the F# route:
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"]
-
Trying the F# route...
Wow - F# is pretty concise!
-
Was thinking something like this to test them, but not sure how to test the non-LISP solutions :|
(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.
-
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.
(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
)
)
)
-
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 :-)
-
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
reverseNths((1,4,5), (0,1,2,3,4,5,6,7))
>>> [0, 5, 2, 3, 4, 1, 6, 7]
reverseNths((5,1,4), (0,1,2,3,4,5,6,7))
>>> [0, 5, 2, 3, 4, 1, 6, 7]
Added bonus:
reverseNths((5,1,4),'abcdefg')
>>> ['a', 'f', 'c', 'd', 'e', 'b', 'g']
-
Nice Python(?) solution Michael!
Your approach sparked an idea:
(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 ]
-
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... :wink:
-
Nice Python(?) solution Michael!
ummm, yeah, guess I should have spec'd what language it was :lol:
Your approach sparked an idea:
(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? :D
-
Nice Python(?) solution Michael!
ummm, yeah, guess I should have spec'd what language it was :lol:
Well, I was pretty sure it was Python, but not 100% :oops:
ain't programming fun? :D
I'm pretty much addicted, yeah
-
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)))
-
If I understand correctly what the outputs should be...C++ version
#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
-
C++ version converted to Python (note pythonic swap (no temp var needed))
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']
-
Nice idea Paul to only perform half the iterations!
-
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());
-
<<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.
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;
}
-
Here's a a final more "C" like version, much cleaner and easier to read.
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;
}
-
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 :)
-
This looks good, Paul
Here's a a final more "C" like version, much cleaner and easier to read.
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;
}