generate permutations of letters in a string

how to generate all permutations of the letters in a string? one method i like, for its intuitiveness - go to the last letter of the string and then recursively create strings by inserting previous letters in all possible positions. at each step a new list of strings will be created, with growing lengths

#include 
#include 
#include 

std::vector permute(std::string s, size_t index) {
    //std::cout << s << " " << index << std::endl;
    std::vector perms;
    if (index >= s.length()) {
        perms.push_back("");
        return perms;
    }
    
    std::string key = s.substr(index, 1);
    std::vector prev = permute(s, index + 1);
    for (size_t i = 0; i < prev.size(); ++i) {
        std::string p = prev[i];
        for (size_t j = 0; j <= p.length(); ++j) {
            std::string n = p.insert(j, key);
            perms.push_back(n);
            p = prev[i];
        }
    }
    return perms;
}

int main()
{
  std::string name = "12345";
  std::vector perms = permute(name, 0);
  for (auto& p : perms) {
    std::cout << p << std::endl;
  }
}

12345
21345
23145
23415
23451
13245
....

Removing Characters from a String

found an interesting learning resource http://www.bogotobogo.com/ it also has a section on programming questions, not so extensive as the awesome http://geeksforgeeks.org/, but has some good problems to solve, with solutions. here is my solution to the "Removing Characters from a String" problem (http://www.bogotobogo.com/cplusplus/quiz_strings_arrays.php). it is not better, just a different approach

#include 
#include 

int main()
{
  std::string name("Ludwig Van Beethoven");
  std::string remove("aeiouAEIOU");
  int walk = 0;
  int last = 1;
  while (last < name.length() && walk < name.length()) {
      auto found = remove.find(name[walk], 0);
      if (found != std::string::npos) {
          char ch = name[walk];
          name[walk] = name[last];
          name[last] = ch;
          ++last;
      } else {
          ++walk;
      }
  }
  std::cout << "Hello, " << name.substr(0, walk+1) << "!\n";
}

remove duplicates from an unsorted linked list

more fun with algorithms: how to remove duplicates from an unsorted linked list in cpp?
easy - just walk along the list and delete duplicate items.
but how to know an item is a duplicate?
well, for every item we could scan the list from the beginning, but this is a ridiculously naive solution - how about keeping all values we encounter while iterating and checking if we have already met a current value?
putting those in an unordered set would be good enough i'd say

#include 
#include 
using namespace std;

struct List {
 int data = 0;
 List* next = nullptr;
 List(int x) : data(x) {}
};

void remove_duplicates(List* head) {
 std::unordered_set cache;
 cache.insert(head->data);
 List* next = head->next;
 while (next != nullptr) {
  if (cache.count(next->data) > 0) {
   head->next = next->next;
   delete next;
   next = head->next;
  } else {
   cache.insert(next->data);
   head = next;
   next = head->next;
  }
 }
}

int main() {
 List* head = new List(1);
 List* list = head;
 for (int index = 2; index < 10; ++index) {
  List* next = new List(index);
  //a silly way to make duplicates in the list
  if (next->data % 2 == 0) {
   next->data = 2;
  } else if (next->data % 3 == 0) {
   next->data = 3;
  }
  list->next = next;
  list = next;
 }
 
 remove_duplicates(head);
 
 while (head != nullptr) {
  printf("%d\n", head->data);
  head = head->next;
 }
 
 return 0;
}

https://ideone.com/K19v5o

reverse linked list

been fooling around writing solutions to algorithms in c++.
here is a solution to reverse a linked list. nothing new - the idea is to revert the links, but before that keep somewhere the links to the nodes to come so that this information is not lost during iterating.
shouldn't have any bugs due to corner cases, i hope :D

#include 
using namespace std;

struct List {
 int value = 0;
 List* next = nullptr;
 List(int x) : value(x) {}
};

List* reverse(List* head) {
 List* next = head->next;
 head->next = nullptr;
 while (next != nullptr) {
  List* movingHead = next->next;
  next->next = head;
  head = next;
  next = movingHead;
 }
 return head;
}

int main() {
 List* head = new List(1);
 List* list = head;
 for (int index = 2; index < 10; index++) {
  List* next = new List(index);
  list->next = next;
  list = next;
 }
 head = reverse(head);
 
 while (head != nullptr) {
  printf("%d\n", head->value);
  head = head->next;
 }
 return 0;
}

https://ideone.com/Wj9ocK

it seems like often it is easier to come up with a recursive solution. here is one: recursively go the the end of the list and then, on winding back, attach "prior" nodes as "next"s to the new head

#include 
using namespace std;

struct List {
 int value = 0;
 List* next = nullptr;
 List(int x) : value(x) {}
};

List* reverse(List* head) {
  List* list = head;
  List* new_head = list;
  if (list->next != nullptr) {
     list = reverse(list->next);
     new_head = list;
     while (list->next != nullptr) {
      list = list->next;
     }
     list->next = head;
     head->next = nullptr;
  }
  return new_head;
}

int main() {
 List* head = new List(1);
 List* list = head;
 for (int index = 2; index < 10; index++) {
  List* next = new List(index);
  list->next = next;
  list = next;
 }
 head = reverse(head);
 
 while (head != nullptr) {
  printf("%d\n", head->value);
  head = head->next;
 }
 return 0;
}

https://ideone.com/Lcfc4r