Name:Unknown
Clan:Unknown
Member Since:May 2018
Last Seen:Jul 2018
Profiles:
Following:0
Followers:0
Allies:0
Objective: given 1 <= K <= 26, 0 <= N count the number of different strings of length N that contain exactly K different characters from the alphabet.
Ideas: for small values of N it should be bruteforce-able.
For large values of N?
Clarifications:
-> "The alphabet" is the 26 lowercase letters of the English alphabet
alphabet = 'abcdefghijklmnopqrstuvwxyz'
import itertools
def counter(N, K):
return counterNaive(N, K)
def counterNaive(N, K):
# print(f"counterNaive({K}, {N})")
allCombs = [x for x in itertools.product(alphabet, repeat=N)]
# print(f"All combinations of length {N}: 26^N = {26**N}")
return sum( len(set(x)) == K for x in allCombs )
def counterSmart(N, K):
# Idea:
# Find all ways of splitting N in K parts
# For each such way, once we know the lenght of the parts K1, ..., Kn
# (And they must be such that K1+...+Kn = N)
# Calculate the possible combinations: they are N!/(N-K)! options for the choice of K letters
# divided by the product of:
# L! where L = count(Kn == j) for j in range(N)
# to compensate the fact that if letters 'a' and 'b' appear in the same amount,
# then doing (a, b) = (b, a) does not give a different sequenec
# times the permutations of N elements with K1, ..., Kn repetitions
# Then add these up
pass# TODO: Replace examples and use TDD development by writing your own tests
# These are some of the methods available:
# test.expect(boolean, [optional] message)
# test.assert_equals(actual, expected, [optional] message)
# test.assert_not_equals(actual, expected, [optional] message)
# You can use Test.describe and Test.it to write BDD style test groupings
Test.describe('Small values of N')
test.assert_equals(counter(1, 1), 26, "There are 26 one-length strings.")
test.assert_equals(counter(3, 1), 26, "If you can only choose one letter, there are always 26 possibilities.")
test.assert_equals(counter(3, 3), 26*25*24, "If K = N, the answer is easy to calculate")
test.assert_equals(counter(3, 2), 26*25*3, "This is the first test with non-trivial N and K")
test.assert_equals(counter(5, 3), 26*25*24*25)
Test.describe('Medium values of N')
#This makes the naive code time out.
#test.assert_equals(counter(20, 8), -1, "Obviously unfinished test")