Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Wortlisten-Generator (Algorithmen)

Schreiben Sie ein Programm, das mehrere Zeichenketten (oder auch Wörter aus Einzelzeichen) entgegen nimmt und daraus alle möglichen Wortkombinationen bildet. Dabei darf jedes Wort in der Ausgabe nur einmal benutzt werden (ansonsten würde die Liste rasch sehr, sehr lange):

Beispiel:

Eingabe Wortvorrat> maria mike auto a b 1 2

Mögliche Ausgabe (die Reihenfolge ist irrelevant):

a12, mariamikeautoab12, ab12, a12b, mike12, abmike, mikeauto, a1bmike, amariab, ...

Nicht im Output aber:

maria3 (enthält falsche Zeichen)

mariamaria (wort kommt doppelt vor)

Bemerkung: Solche Algorithmen können leicht verwendet werden, um mittels Rainbow-Tables Passwörter zu knacken. Vermeiden Sie also in Ihren eigenen Passwörtern --- wenn immer möglich --- das Auftreten sinnvoller Wörter.

0 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

7 Lösung(en)

/*
von Ruben S.
*/
#include <iostream>
#include <stdlib.h>  
#include <string>
#include <vector>
#include <time.h>  

using std::cout;
using std::endl;
using std::cin;

class wordlistgen
{
public:
	wordlistgen();
	~wordlistgen();

	std::string swap_Index(int &index);

private:
	std::string Input;
	std::vector<std::string> vecWords;
};

wordlistgen::wordlistgen()
{
	cout << "Eingabe: ";
	std::getline(cin, Input);
	Input.push_back(' ');

	std::string * str = NULL;
	str = new std::string;

	//woerter erkennen
	for (std::string::iterator it = Input.begin(); it != Input.end(); ++it){
		if (*it != ' '){
			str->push_back(*it);
		}
		else{
			vecWords.push_back(*str);
			str = new std::string;
		}
	}

	for (int stage = 0; stage < 4; stage++){ //verstellbar 4 = bis zu 4er Kombinationen, 3 bis zu...
		for (int y = 0; y < vecWords.size(); y++){
			std::string output = (y == 0 ? vecWords[y] : swap_Index(y));
			if (stage > 0){
				for (int u = 0; u < vecWords.size() - 1; u++){
					output = vecWords[0];
					output += vecWords[u + 1];
					if (stage >= 2){ //fuer 3er Kombi
						for (int i = 1; i < vecWords.size(); i++){
							if (i != u + 1){ //herausfiltern der bereits benutzten woerter
								output = vecWords[0];
								output += vecWords[u + 1];
								output += vecWords[i];
								if (stage == 3){ //fuer 4er Kombi
									for (int d = 1; d < vecWords.size(); d++){
										if (d != 0 && d != u + 1 && d != i){ //herausfiltern...
											output = vecWords[0];
											output += vecWords[u + 1];
											output += vecWords[i];
											output += vecWords[d];
											cout << output << endl;
										}
									}
								}
								else{
									cout << output << endl;
								}
							}
						}
					}
					if (stage < 2){
						cout << output << endl;
					}
				}
			}
			else{
				cout << output << endl;
			}
		}
	}

	cout << "Du hast " << vecWords.size() << " Woerter eingegeben." << endl;
	cout << "                       Kombinationen        " << endl;
	cout << "Anzahl Woerter| 1er | 2er | 3er | 4er |     " << endl;
	cout << "--------------|-----|-----|-----|-----|-----" << endl;
	cout << "       1      |  1  |  0  |  0  |  0  |     " << endl;
	cout << "--------------|-----|-----|-----|-----|-----" << endl;
	cout << "       2      |  2  |  2  |  0  |  0  |     " << endl;
	cout << "--------------|-----|-----|-----|-----|-----" << endl;
	cout << "       3      |  3  |  6  |  6  |  0  |     " << endl;
	cout << "--------------|-----|-----|-----|-----|-----" << endl;
	cout << "       4      |  4  |  12 |  24 |  24 |     " << endl;
	cout << "--------------|-----|-----|-----|-----|-----" << endl;
	cout << "       5      |  5  |  20 |  60 | 120 |     " << endl;
	cout << "--------------|-----|-----|-----|-----|-----" << endl;
	cout << "              |     |     |     |     |     " << endl;

	system("PAUSE");
}


std::string wordlistgen::swap_Index(int &index)
{
	std::string save = vecWords[0]; //0 wird zwischengespeichert
	vecWords[0] = vecWords[index]; //0 wird zum index
	vecWords[index] = save; //index wird zum 0

	return vecWords[0];
}

wordlistgen::~wordlistgen(){}

int main()
{
	wordlistgen GEN;
}

                

Lösung von: Ruben Sidon (WRG Bendorf)

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Created by linus on 16.10.17.
 */
public class Main {

    public static void main(String[] args) {
        new Main().init();
    }

    private void init() {
        List<String> combinations = generateWords(read());
        print(combinations);
    }

    private String[] read() {
        System.out.print("Eingabe: ");
        Scanner scanner = new Scanner(System.in);
        return scanner.nextLine().split(" ");
    }

    private List<String> generateWords(String[] words) {
        return loop(words, new ArrayList<>(), new ArrayList<>(), 1);
    }

    private List<String> loop(String[] words, List<String> current, List<String> combinations, int loop) {
        for(int i = 0; i < words.length; i++) {
            if(!current.contains(words[i])) {
                current.add(words[i]);

                StringBuilder stringBuilder = new StringBuilder();
                current.forEach(stringBuilder::append);
                combinations.add(stringBuilder.toString());

                if(loop != words.length) {
                    loop(words, current, combinations, loop + 1);

                    if(current.size() > 0) {
                        current.remove(current.size() - 1);
                    }
                }
            }

            if(i == words.length - 1 && current.size() > 0 && loop == words.length) {
                current.remove(current.size() - 1);
            }
        }

        return combinations;
    }

    private void print(List<String> list) {
        System.out.println();
        System.out.println("Anzahl der Kombinationen: " + list.size());
        System.out.println("Kombinationen:");

        for(String s : list) {
            System.out.println(s);
        }
    }
}

                

Lösung von: Name nicht veröffentlicht

import itertools

words = input('gimme some cool words: ')

list_of_words = words.split(' ')

print('possible permutations are: ')

for i in range(0, len(list_of_words)):
    possible_permutations = itertools.permutations(list_of_words, i + 1)
    for j in possible_permutations:
        s = ''
        for k in j:
            s = s + k
        print(s)

                

Lösung von: Ich Bins (tubs)

using System;
using System.Collections.Generic;
using System.Linq;

namespace WortKreuzen
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Gebe die Wörter/Zeichen mit Leertaste getrennt ein:");
            string[] Kette = Console.ReadLine().Split(' ');

            List<string> Möglichkeiten = new List<string>();

            //Für jedes Wort in der Kette (Erstes Wort)
            for(int i = 0; i < Kette.Length; i++)
            {
                Möglichkeiten.Add(Kette[i]);

                //Füge jedes mal ein weiteres Wort zur Kontrollvariable hinzu (Jeden Durchlauf ein weiteres Wort an das erste setzen)
                for (int l = 0; l < Kette.Length; l++)
                {
                    string Wort = Kette[i];

                    if (!Wort.Contains(Kette[l]))
                    {
                        Wort += Kette[l];
                        if (!Möglichkeiten.Contains(Wort)) Möglichkeiten.Add(Wort);
                    }

                    //Setze hinter die zuvor geschaffene Kontrollvariable jedes andere Wort aus der Liste und prüfe, ob dieses bereits existiert.
                    for (int k = 0; k < Kette.Length; k++)
                    {
                        if (!Wort.Contains(Kette[k]))
                        {
                            Wort += Kette[k];
                            if(!Möglichkeiten.Contains(Wort)) Möglichkeiten.Add(Wort);
                        }
                    }
                }
            }


            foreach(var item in Möglichkeiten)
            {
                Console.WriteLine(item);
            }
            Console.ReadLine();
        }
    }
}

                

Lösung von: Tobias Golz (Wilhelm Büchner Hochschule)

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        //Initialisierung und Deklaration der benötigen Variablen/Objekten
        Scanner reader = new Scanner(System.in);
        String input; //Zum Speichern der User-Eingabe
        String[] strings; //Array für die einzelnen Zeichenketten, die der User eingibt.
        int inputStringPointer = 0; //Hilfsvariable. "Zeigt" auf ein Element in dem strings[]-Array
        List<String> concatStrings = new ArrayList<String>(); //Speichert die neuen Zeichenketten ab.
        int concatStringPointer = 0; //Hilfsvariable. "Zeigt" auf das letzte Element in der concatStrings-Liste.
        boolean next = true; //Hilfsvariable.

        //Einlesen der Zeichenketten
        System.out.println("Gebe distinkte Zeichenketten an: ");
        input = reader.nextLine();
        strings = input.split(" ");
        reader.close();

        /*
        Es werden alle Zeichenketten konkateniert, in beliebiger Reihenfolge und beliebiger Anzahl von Zeichenketten für die Konkatenation,
        aber keine Wiederholungen. Es wird sich die erste Zeichenkette x aus dem strings-Array gegriffen und jede Kombination, die mit x anfangen könnte,
        wird erstellt. Das selbe wird mit der nächsten Zeichenkette gemacht, bis alle Zeichenketten durchgegangen wurden.
         */
        while (inputStringPointer < strings.length) {
            if (next) {
                concatStrings.add(strings[inputStringPointer]);
                next = false;
            } else {
                String newString = concatStrings.get(concatStringPointer);
                for (String s : strings) {
                    if(!newString.contains(s)) {
                        concatStrings.add(newString + s);
                    }
                }
                if (concatStringPointer == concatStrings.size()-1) {
                    next = true;
                    inputStringPointer++;
                } else {
                    concatStringPointer++;
                }
            }
        }

        System.out.println(concatStrings);
    }

}

                

Lösung von: Daniel Figia (Technische Hochschule Lübeck)

/*********************************************************************\
| Hier der kern des ganzen:                                           |
| Anhand des musters der binärzahlen von bspw. 0001 bis 1111 werden   |
| die wörter des vorrats ausgewählt und deren permutationen auf die   |
| liste gesetzt.                                                      |
\*********************************************************************/
// erwartet einen string, der anhand seiner leerzeichen in
// ein array zerlegt wird
let ComposedList = function(stock) {
  stock = stock.split(' ');
  let out = [],
      lim = 2 ** stock.length - 1, // obergrenze der wortauswahlen
      i, j;
  for (i = 1; i <= lim; i++) {
    let tmpArr = [],
        bin = leadZeroes(i.toString(2), stock.length); // 0001 - 1111
    // muster auf die wortauswahl anwenden
    for (j = 0; j < bin.length; j++)
      if (bin[j] == '1') tmpArr.push(stock[j]);
    // wortauswahl permutieren und ab auf die liste
    // leerversuche werden ausgesiebt
    let perms = permute(tmpArr);
    for (j = 0; j <= perms.length; j++)
      if (perms[j] != undefined) out.push(perms[j].join(''));
  }
  return out;
}
/********************************************************************/

// der rest ist technisches hilfswerk:
// a) array permutieren
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;
}

// b) führende nullen
function leadZeroes(str, len) {
  while (str.length < len) str = '0' + str;
  return str;
}

// test
let myList = new ComposedList('Maria Mike Auto A B 1 2');
console.log(`${myList.length} Kombinationen generiert:`);
console.table(myList);

                

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

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

std::vector<std::string> get_wordList(const std::vector<std::string>& in_) {
    std::vector<std::string>out_{};
    for (auto i{ 0 }; i < in_.size(); i++) {
        std::vector<std::string> tmp_{};
        for (auto k{ i }; k < in_.size(); k++) {
            tmp_.push_back(in_[k]);
            std::sort(tmp_.begin(), tmp_.end());
            do {
                std::string per_{};
                for (const auto& t : tmp_) per_ += t;
                out_.push_back(per_);
            } while (std::next_permutation(tmp_.begin(), tmp_.end()));
        }
    }
    return out_;
}

int main() {
    const std::vector<std::string> v{ "maria", "mike", "auto", "a", "b", "1", "2" };
    auto wl{ get_wordList(v) };
    std::cout << "Anzahl Kombinationen: " << wl.size() << "\nKombinationen:\n";
    for (const auto& w : wl) std::cout << w << "\n";
}
                

Lösung von: Jens Kelm (@JKooP)

Verifikation/Checksumme:

Eingabe Wortvorrat> 123

Ausgabe

1, 2, 3, 12, 21, 13, 31, 23, 32, 123, 132, 213, 231, 312, 321

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 2
Schwierigkeit: Schwer
Webcode: ankq-6hca
Autor: ()

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen