Mam nastepujący problem. Mam danych n ciągów liter, ciągi te mają różne liczby elementów. Mam znaleźć ile będzie 3 literowych wyrazów, litery te muszą pochodzić od różnych ciągów, nie mogą to być 2 litery z tego samego ciągu, lub 3 litery z tego samego ciągu.
Oto przykład :
Ciągi :
abc
de
fghi
jk
Wynik : 76 (przykładowe słowa : adf, jga,kdb )
Jak to najłatwiej wyliczyć ?
0
1
W 26 bitach możesz zakodować litery użyte w każdym ze słów.
Trzy włożone pętle od 'a' do 'z' każda to chyba też nie problem.
Kodujesz na 26 bitach każdą 3 literową możliwość.
Sprawdzasz czy z którymś z zakodowanych słów nie ma wspólnych 2 bitów.
C=A&B;
if(C&(C-1)) // then A i B mają więcej niż 1 wspólny bit
Tak a propos, wynik 76 jest ewidentnie niepoprawny.
Ponieważ jeżeli pasuje: adf
to pasują również afd, daf, dfa, fad, fda
Czyli wynik musi być krotny 6.
1
Każdy z twoich n-ciągów pozwala na tyle możliwości ile ma elementów. Musisz przelecieć wszystkie 3 elementowe kombinacje ciągów i dla każdej policzyć iloczyn liczby elementów w wybranych ciągach. Sumujesz te iloczyny i voila. To przy założeniu że ciągi nie mają elementów wspólnych ofc. Jeśli mogą takowe mieć to musisz po wybraniu 3 ciągów usunąć duplikaty i dopiero wtedy liczyć iloczyn.
0
Zbiory są rozłączne.