Programmieren lernen

public class Reisegruppe {
  public static void main(String[] args) {
    new Reisegruppe().top(); }

  void top() {
    Permutationen ps = new Permutationen(); 
    int[] sehenswuerdigkeiten;
    int anzahlTouren;
    
    System.out.println("Aufgabe a)");
    sehenswuerdigkeiten = new int[] {1,2,3,4};
    ps.ausgabe(sehenswuerdigkeiten);
    while(ps.hatNaechstePermutation(sehenswuerdigkeiten)) {
       ps.naechstePermutation(sehenswuerdigkeiten);
       ps.ausgabe(sehenswuerdigkeiten); }
      
    
    System.out.println("Aufgabe b)");
    sehenswuerdigkeiten = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
    anzahlTouren = 1;
    ps.ausgabe(sehenswuerdigkeiten);
    while(ps.hatNaechstePermutation(sehenswuerdigkeiten)) {
        anzahlTouren = anzahlTouren + 1;
        ps.naechstePermutation(sehenswuerdigkeiten); 
        ps.ausgabe(sehenswuerdigkeiten); }
    System.out.println("Aufgabe b: Total der Touren: " + anzahlTouren);
    
    System.out.println("Aufgabe c)");
    sehenswuerdigkeiten = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
    anzahlTouren = 0;
    while(ps.hatNaechstePermutation(sehenswuerdigkeiten)) {
        if(1 == abstand(1, 2, sehenswuerdigkeiten))  {
            anzahlTouren = anzahlTouren + 1;
            ps.ausgabe(sehenswuerdigkeiten);  }
        ps.naechstePermutation(sehenswuerdigkeiten);  }
    if(1 == abstand(1, 2, sehenswuerdigkeiten))  {
        anzahlTouren = anzahlTouren + 1;
        ps.ausgabe(sehenswuerdigkeiten); }
    System.out.println("Aufgabe c: Total der Touren: " + anzahlTouren);
    
    System.out.println("Aufgabe d)");
    sehenswuerdigkeiten = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
    anzahlTouren = 0;
    while(ps.hatNaechstePermutation(sehenswuerdigkeiten)) {
        if(1 == abstand(1, 2, sehenswuerdigkeiten) &&
           4 <= abstand(1, 3, sehenswuerdigkeiten))   {
            anzahlTouren = anzahlTouren + 1;
            ps.ausgabe(sehenswuerdigkeiten);  }
        ps.naechstePermutation(sehenswuerdigkeiten);  }
    if(1 == abstand(1, 2, sehenswuerdigkeiten) &&
            4 <= abstand(1, 3, sehenswuerdigkeiten))   {
             anzahlTouren = anzahlTouren + 1;
             ps.ausgabe(sehenswuerdigkeiten);  }
    System.out.println("Aufgabe d: Total der Touren: " + anzahlTouren);
 
    
  } // end method top();
  
   int abstand(int a, int b, int[] sehenswuerdigkeiten) {
     int posA;
     int posB;
     posA = findPos(a, sehenswuerdigkeiten);
     posB = findPos(b, sehenswuerdigkeiten);
     if(posA < posB) {
        return posB - posA; }
     else {
        return posA - posB; }
   } // end method: abstand

   
   int findPos(int a, int[] sehenswuerdigkeiten) {
     int checkPos;
     checkPos = 0;
     while(checkPos < sehenswuerdigkeiten.length) {
        if(a == sehenswuerdigkeiten[checkPos]) {
            return checkPos;        }
        checkPos = checkPos + 1; }
     return -1; // error, darf nicht passieren!
   }
    
   
   
  
}  // end of class Schulreise



import java.util.Arrays;


public class Permutationen {

   public static void main(String args []) {
       new Permutationen().test();
   }
    
   void test() {
       // Initialpermutation muss aufsteigend sein.
       int permut[] = {1, 3, 4, 6, 9};
       ausgabe(permut);
       while(naechstePermutation(permut)) {
           ausgabe(permut);
       }
   }
    
   void ausgabe(int [] arr) {
       for(int val : arr) {
           System.out.print(val + "");           
       }
       System.out.println();
   }
   
   boolean hatNaechstePermutation(int [] permutation) {
       int aktPos = permutation.length - 1;
       while(aktPos > 0) {
           if(permutation[aktPos - 1] < permutation[aktPos]) {
               return true;
           }
           aktPos = aktPos - 1;
       }
       return false;
   }
   
   /** 
    * Suche numerisch die nächstgrößere Permutation
    * @return false, wenn es bereits die letzte Permutation war.
    */
   boolean naechstePermutation(int[] permutation) {
        int aktPos = permutation.length - 1;
        while(aktPos > 0) {
            if(permutation[aktPos - 1] < permutation[aktPos]) {
                neuOrdnen(permutation, aktPos - 1);
                return true;
            }
            aktPos = aktPos - 1;
        }
        return false;
   }

   /**
    * Beispiel: 123956874
    * Eingabe startPosition: Gegeben ist die Startposition, wo zum ersten mal "<" auftaucht.
    * Im Beispiel die Position, wo die "6" steht: 123956<8>7>4
    * 
    * 1. Finde den minimalen Tauschpartner:
    *    Nennen wir die Zahl an position "startPosition" kurz "startWert".
    *    (in Obigem beispiel: StartWert = 6)
    *    Der Tauschpartner ist die kleinset Zahl rechts der startPosition, die aber größer als der
    *    startWert ist. (im Beispiel 7)
    *    Die Position, wo die "7" steht, nennen wir "naechstesfureStartPos".
    * 2. Tausche "7" mit "6".
    * 3. Sortiere ab >startPos aufsteigend. 
    * 
    */
   void neuOrdnen(int[] permutation, int startPosition) {
        int naechstesFuerStartPos = findeMinimalenTauschpartner(permutation, startPosition);
        tausche(permutation, startPosition, naechstesFuerStartPos);
        sortiereAb(permutation, startPosition + 1);  
   }

   /**
    * Ab "startPosition" soll aufsteigend sortiert werden.
    * @param permutation
    * @param startPosition
    */
   void sortiereAb(int[] permutation, int startPosition) {
        Arrays.sort(permutation, startPosition, permutation.length);
   }


   void tausche(int[] permutation, int a, int b) {
        int temp       = permutation[a];
        permutation[a] = permutation[b];
        permutation[b] = temp;
   }

   /**
    * Siehe doku "neuOrdnen()"
    */
   int findeMinimalenTauschpartner(int[] permutation, int referenzPosition) {
        int referenzWert = permutation[referenzPosition];
        int min = Integer.MAX_VALUE; // next
        int minPos = -1;
        int i = referenzPosition + 1;
        while(i < permutation.length)
        {
          int actValue = permutation[i];
          if(min > actValue && actValue > referenzWert) {
             min = actValue;
             minPos = i;
          }
          i = i + 1;
        }
        return minPos;
   }
   
} // end of class NextPermutation
                

// https://stackoverflow.com/questions/9960908/permutations-in-javascript
// die schnellste und robusteste funktion, die ich jemals zum thema
// gefunden habe.
function permute(arr) {
  let length = arr.length,
      result = [arr.slice()],
      c = new Array(length).fill(0),
      i = 1, k, p;
  while (i < length) {
    if (c[i] < i) {
      k = i % 2 && c[i];
      p = arr[i];
      arr[i] = arr[k];
      arr[k] = p;
      ++c[i];
      i = 1;
      result.push(arr.slice());
    } else {
      c[i] = 0;
      ++i;
    }
  }
  return result;
}

let pois, tours;

// a)
console.log('a)');
pois = [1, 2, 3, 4];
tours = permute(pois);
console.table(tours);
console.log(tours.length);

// b)
pois = [1, 2, 3, 4, 5, 6, 7, 8, 9];
tours = permute(pois);
console.log(tours.length);

// c)
let tours12 = [],
    tmp;
for (let i = 0; i < tours.length; i++) {
  tmp = tours[i];
  if (Math.abs(tmp.indexOf(1) - tmp.indexOf(2)) == 1) tours12.push(tmp);
}
console.log(tours12.length);

// d)
let tours13 = [];
for (i = 0; i < tours12.length; i++) {
  tmp = tours12[i];
  if (Math.abs(tmp.indexOf(3) - tmp.indexOf(1)) >= 4) tours13.push(tmp);
}
console.log(tours13);
console.log(tours13.length);

                

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)

// C++ 14 | VS-2022
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::vector<std::string> get_all_tours(const std::string& str) {
    std::vector<std::string> tmp{};
    std::string s{ str };
    do {
        tmp.push_back(s);
    } while (std::next_permutation(s.begin(), s.end()));
    return tmp;
}

void print(const std::vector<std::string>& v) {
    for (const auto& i : v)
        std::cout << i << "\n";
}

template<typename Type, typename Func>
Type get_special_tours(Type t, Func f) {
    Type tmp{};
    for (const auto& s : t)
        if (f(s)) tmp.push_back(s);
    return tmp;
}

int main() {
    const auto dif{ [](auto s, auto a, auto b) {return abs((int)s.find(a) - (int)s.find(b)); } };

    const std::string sights_a{ "1234" };
    const auto tour_a{ get_all_tours(sights_a) };
    std::cout << "a) " << tour_a.size() << "\nmoegliche Touren:\n";
    print(tour_a);

    const std::string sights_b{ "123456789" };
    const auto tour_b{ get_all_tours(sights_b) };
    std::cout << "\nb) " << tour_b.size() << "\nmoegliche Touren:\n";
    //print(tour_b); // bei Bedarf!

    const auto tour_c{ get_special_tours(tour_b, [&dif](auto s) { return dif(s, '2', '1') == 1; }) };
    std::cout << "\nc) " << tour_c.size() << "\nmoegliche Touren:\n";
    //print(tour_c); // bei Bedarf!

    const auto tour_d{ get_special_tours(tour_c, [&dif](auto s) { return dif(s, '3', '1') >= 4; }) };
    std::cout << "\nd) " << tour_d.size() << "\nmoegliche Touren:\n";
    //print(tour_d); // bei Bedarf!
}
                

Lösung von: Jens Kelm (@JKooP)