Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
FIT3155 Assignment
(i) The number of strings of length N from alphabet A with ≥ 2 distinct cyclic
rotations.
(ii) The number of strings of length N from alphabet A with exactly N distinct
cyclic rotations.
(iii) The number of strings of length N from alphabet A with exactly 1 distinct cyclic
rotation.
(iv) Is the number of strings with ≥ 2 distinct cyclic rotations an integer multiple of
N? If yes, print true, else print false.
Sample outputs (with supporting debug information, which you do not have to report)
(SAMPLE 1) Input values:
2 4
Output:
14 12 2 false
---------------------------------------------------------------------------------------------
Debug information for |A| = 2 and N = 4:
2
cyclicrotations(aaaa) | cyclicrotations(abaa) | cyclicrotations(baaa) | cyclicrotations(bbaa)
aaaa | abaa | baaa | bbaa
aaaa | baaa | aaab | baab
aaaa | aaab | aaba | aabb
aaaa | aaba | abaa | abba
nDistinct = 1 | nDistinct = 4 | nDistinct = 4 | nDistinct = 4
cyclicrotations(aaab) | cyclicrotations(abab) | cyclicrotations(baab) | cyclicrotations(bbab)
aaab | abab | baab | bbab
aaba | baba | aabb | babb
abaa | abab | abba | abbb
baaa | baba | bbaa | bbba
nDistinct = 4 | nDistinct = 2 | nDistinct = 4 | nDistinct = 4
cyclicrotations(aaba) | cyclicrotations(abba) | cyclicrotations(baba) | cyclicrotations(bbba)
aaba | abba | baba | bbba
abaa | bbaa | abab | bbab
baaa | baab | baba | babb
aaab | aabb | abab | abbb
nDistinct = 4 | nDistinct = 4 | nDistinct = 2 | nDistinct = 4
cyclicrotations(aabb) | cyclicrotations(abbb) | cyclicrotations(babb) | cyclicrotations(bbbb)
aabb | abbb | babb | bbbb
abba | bbba | abbb | bbbb
bbaa | bbab | bbba | bbbb
baab | babb | bbab | bbbb
nDistinct = 4 | nDistinct = 4 | nDistinct = 4 | nDistinct = 1
---------------------------------------------------------------------------------------------
(SAMPLE 2) Input values:
3 3
Output:
24 24 3 true
---------------------------------------------------------------------------------------------
Debug information for |A| = 3 and N = 3:
cyclicrotations(aaa) | cyclicrotations(acb) | cyclicrotations(bbc) | cyclicrotations(cba)
aaa | acb | bbc | cba
aaa | cba | bcb | bac
aaa | bac | cbb | acb
nDistinct = 1 | nDistinct = 3 | nDistinct = 3 | nDistinct = 3
cyclicrotations(aab) | cyclicrotations(acc) | cyclicrotations(bca) | cyclicrotations(cbb)
aab | acc | bca | cbb
aba | cca | cab | bbc
baa | cac | abc | bcb
nDistinct = 3 | nDistinct = 3 | nDistinct = 3 | nDistinct = 3
cyclicrotations(aac) | cyclicrotations(baa) | cyclicrotations(bcb) | cyclicrotations(cbc)
aac | baa | bcb | cbc
aca | aab | cbb | bcc
caa | aba | bbc | ccb
nDistinct = 3 | nDistinct = 3 | nDistinct = 3 | nDistinct = 3
cyclicrotations(aba) | cyclicrotations(bab) | cyclicrotations(bcc) | cyclicrotations(cca)
aba | bab | bcc | cca
baa | abb | ccb | cac
aab | bba | cbc | acc
nDistinct = 3 | nDistinct = 3 | nDistinct = 3 | nDistinct = 3
cyclicrotations(abb) | cyclicrotations(bac) | cyclicrotations(caa) | cyclicrotations(ccb)
abb | bac | caa | ccb
bba | acb | aac | cbc
bab | cba | aca | bcc
nDistinct = 3 | nDistinct = 3 | nDistinct = 3 | nDistinct = 3
cyclicrotations(abc) | cyclicrotations(bba) | cyclicrotations(cab) | cyclicrotations(ccc)
abc | bba | cab | ccc
bca | bab | abc | ccc
cab | abb | bca | ccc
nDistinct = 3 | nDistinct = 3 | nDistinct = 3 | nDistinct = 1
cyclicrotations(aca) | cyclicrotations(bbb) | cyclicrotations(cac) |