Problem of the Day -- Unique Permutations

Unique Permutations

Today's problem comes from @mofodox.

Given the string "Hello world hello" how many unique (case sensitive) permutations can you find?

If you have a problem you'd like to see featured on here head over to http://www.problemotd.com/suggest/ and suggest it now!

Permalink: http://problemotd.com/problem/unique-permutations/

Comments:

Anonymous - 10 years, 9 months ago
2^15

reply permalink
Zing - 10 years, 9 months ago
17! / (2! 5! 3! 2!) = 123502579200

reply permalink
heartinpiece - 10 years, 9 months ago
Yup, I came up with this answer, just that I forgot the spaces, and thus had 15!/(2!5!3!) Which is semantically wrong :)

reply permalink
Carlos - 10 years, 9 months ago
Don't be stupid as i was and read "UNIQUE permutations", the answer is indeed: 17! / (2 * 2 * 5! * 3!)

reply permalink
Shay - 10 years, 9 months ago
This problem is really ill-phrased... is it permutation of characters? of words? does it include whitespaces?

Disappointing qotd...

reply permalink
Anonymous - 10 years, 9 months ago
This was my thought. Really poorly defined question. An answer that has to be accepted is 6.

reply permalink

tehMagik - 10 years, 9 months ago

for the sake of coding, the # of permutations:

def FindNumberOfPermutations(word):
    dividend = math.factorial(len(word))
    divisor = 1
    letterCount = CountCharacters(word).values()
    for count in letterCount:
        divisor = divisor * math.factorial(count)
    return dividend / divisor

def CountCharacters(word):
    letters = {}
    for letter in word:
        if letter not in letters:
            letters[letter] = 1
        else:
            letters[letter] += 1
    return letters


permutationCount = FindNumberOfPermutations("Hello world hello")

print(permutationCount)

Finding all the actual permutations: def FindPermutations(originalWord, currWord=""): global permList if len(originalWord) == 1: currWord += originalWord permList.append(currWord) return for i in range(0,len(originalWord)): perm = currWord + originalWord[i] FindPermutations(originalWord[0:i]+originalWord[i+1:], perm)

def RemoveDuplicates(item):
    return list(set(item))

reply permalink

tehMagik - 10 years, 9 months ago
yeah...it'd be nice if we could just throw <code> in there instead of having to spam spaces. captcha is pretty damn annoying too.

reply permalink
Max Burstein - 10 years, 9 months ago

I'm working on getting a more advanced version of markdown implemented (similar to Github's) which will fix the indentation issue. Authentication is also on the todo list so you won't need to fill in a captcha each time. Hopefully I'll get some time this weekend to knock out a few things.

Thanks for your submission!

reply permalink
tehMagik - 10 years, 9 months ago
cool, thanks!

reply permalink

Jubyjoo - 10 years, 9 months ago

Hit em up with some of this:

#!/usr/bin/env python3

import itertools


def gap(s, ind):
    """
    print string *s* without letter at index *ind*
    """
    g = s[:ind] + s[ind+1:]
    return g

def distribute(letter, rest_list):
    """
    *rest_list* is list of strings, *letter* is string length 1, append *letter* in front of each of *rest_list*
    return resulting list same length
    """

    acc = []
    for i in rest_list:
        n = letter + "".join(i)
        acc.append(n)
    return acc

def permute(s):
    if len(s) <= 1:
        return list(s)
    else:
        acc = []
        for i in range(len(s)):
            acc.append( distribute(s[i],
                                   permute(gap(s,i))))
        # flatten list of lists here
        merged = list(itertools.chain.from_iterable(acc))
        return merged

s = "Hello world hello"
ret = permute(s)
for i in ret:
    print(i)

reply permalink

Problem of the Day A new programming or logic puzzle every Mon-Fri

Unique Permutations

Comments:

Problem of the Day
A new programming or logic puzzle every Mon-Fri