diff options
Diffstat (limited to 'bonusaufgabe/src')
| -rw-r--r-- | bonusaufgabe/src/main.rs | 51 |
1 files changed, 46 insertions, 5 deletions
diff --git a/bonusaufgabe/src/main.rs b/bonusaufgabe/src/main.rs index 3c9255d..f5983bc 100644 --- a/bonusaufgabe/src/main.rs +++ b/bonusaufgabe/src/main.rs @@ -8,6 +8,7 @@ use std::process; type Card = BitVec; // Typ, der eine zu lösende Aufgabe beschreibt. +#[derive(Clone)] // TODO remove struct Task { cards: Vec<Card>, num_pass_cards: usize, @@ -75,6 +76,8 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut // `ppcm` ist eine solche Kontrollmatrix (repräsentiert als Iliffe-Vektor), // auf dessen Spalten zusätzlich noch die Permutation `permutation` // angewandt wurde. + // + // O(bits_per_card num_cards) let mut ppcm = transpose_and_optionally_permute_columns(cards, Some(&permutation)); // `basic_vars` und `free_vars` enthalten jeweils die Spaltenindizes der @@ -86,11 +89,15 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut // Zunächst wird `ppcm` mittels des Gaußschen Eliminierungsverfahrens // in die reduzierte Stufenform gebracht. + // + // O(bits_per_card^2 num_cards) let mut current_row = 0; let mut current_col = 0; while current_row < bits_per_card && current_col < num_cards { + // O(bits_per_card) // Wir suchen in der derzeitigen Spalte ein Pivotelement (eine 1). let pivot_row = match (current_row..bits_per_card).find(|row| ppcm[*row][current_col]) { + // O(bits_per_card) worst-case Some(row) => row, None => { // Wurde kein Pivotelement gefunden, gehört diese Spalte zu @@ -111,9 +118,10 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut // indem die entsprechenden Zeilen mit der Zeile des Pivotelements XOR // gerechnet (addiert) werden. for lower_row in (current_row + 1)..bits_per_card { + // O(bits_per_card) if ppcm[lower_row][current_col] { let current_row_cloned = ppcm[current_row].clone(); - ppcm[lower_row] ^= current_row_cloned; + ppcm[lower_row] ^= current_row_cloned; // O(num_cards) } } // Es kann zur nächsten Zeile und Spalte übergegangen werden. @@ -137,11 +145,15 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut // Einsen werden eliminiert, indem die entsprechenden Zeilen mit der Zeile // des Pivotelements XOR gerechnet (addiert) werden. Diese Erweiterung // wird auch als Gauß-Jordan-Algorithmus bezeichnet. + // + // O(bits_per_card^2 num_cards) for (pivot_row, pivot_col) in basic_vars.iter().enumerate().rev() { + // O(bits_per_card) for upper_row in 0..pivot_row { + // O(bits_per_card) if ppcm[upper_row][*pivot_col] { let pivot_row_cloned = ppcm[pivot_row].clone(); - ppcm[upper_row] ^= pivot_row_cloned; + ppcm[upper_row] ^= pivot_row_cloned; // O(num_cards) } } } @@ -161,12 +173,16 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut // Zunächst wird die Matrix transponiert, damit die Bits der Spalten // jeweils zusammenhängend im Speicher liegen und somit die Spalten // schneller miteinander XOR gerechnet werden können. + // + // O(bits_per_card num_cards) let transposed_ppcm = transpose_and_optionally_permute_columns(&ppcm, None); // Um die `p` freien Variablen mit dem Wert 1 zu finden, wird über alle // möglichen `p`-Untermengen der freien Variablen iteriert und jeweils // angenommen, dass von den freien Variablen nur die in der Untermenge den // Wert 1 haben. + // + // O(k choose p) let mut subset_iter = SubsetIterator::new(num_free_vars, p); while let Some(subset) = subset_iter.next() { // Zunächst wird das exklusive Oder der `p` Spalten in der Untermenge @@ -204,7 +220,7 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut } } - // Von den freien Variablen hatten nicht genau `p` den Wert 1. Die + // Von den freien Variablen hatten nicht genau `p` den Wert 1. Diese // Iteration ist fehlgeschlagen, und in der nächten Iteration wird eine // andere Spaltenpermutation und somit auch eine andere Auswahl freier // Variablen probiert. @@ -318,8 +334,33 @@ fn main() { let task_str = fs::read_to_string(task_file_name).expect("Datei kann nicht gelesen werden"); let task = Task::try_from(task_str.as_str()).expect("Datei enthält keine gültige Aufgabe"); - let solution = solve_task(task); - print!("{}", solution); + // let solution = solve_task(task); + // print!("{}", solution); + + let mut task = task; + + loop { + use rand::prelude::*; + let solution = solve_task(task.clone()); + print!("{}", solution); + + let num_rand_cards = task.cards.len() - task.num_pass_cards - 1; + let bits_per_card = task.cards[0].len(); + let mut new_rand_cards = (0..num_rand_cards) + .map(|_| { + rand::thread_rng() + .sample_iter::<bool, rand::distributions::Standard>( + rand::distributions::Standard, + ) + .take(bits_per_card) + .collect::<BitVec>() + }) + .collect::<Vec<BitVec>>(); + let mut new_cards = solution.real_cards; + new_cards.append(&mut new_rand_cards); + new_cards.shuffle(&mut rand::thread_rng()); + task.cards = new_cards + } } // Liest eine Aufgabe im Format der Beispielaufgaben ein. |