kiice5 kiice5 - 1 year ago 70
Python Question

How to find permutations in a list then remove them?

I'm trying to find a permutation of another number in this txt file and then add them to a list:


In this file, the permutations are 491 and 194.

This is my code:

numberList = []

file = open("file.txt", "r")
for line in file:

Now they're added to
, how do I remove them (491 and 194) from this list.

Answer Source

Ok, let's do a bit of group theory:

assume you can decompose your numbers x into digits X[i] (removing the \n is really trivial, and surely someone else will cover this).

Then we know that, by how the decimal system works,

$$x = \sum_{i=0}^{\log_{10} x} x[i] 10^i$$

what we need to find is a function y=f(x) that maps x'es that are permutations of the same number to the same y, but x'es that aren't permutations to different y.

we can use the fact that the prime factorization of different numbers is different, and simply find the sum over exponents of a prime that isn't a digit (and larger than the length of the number*digits). This get's easier if we assume less than 9 digits, so we'll do that.

for this example, let's stick to 17 (which further limits our number of digits, but oh well).

$$y= f(x) = \sum_{i=0}^{6} 17^x$$

so, now you'd use that function as comparison key in a python set and be done.

So, very naively (and very untested):

class permutation(object):
    def __init__(self, x):
         we'll assume x is an integer
         digits = str(x)
         self.original = x
         self._hash = sum([17**int(digit) for digit in digits])
    def __hash__(self):
         return self._hash
    def __eq__(self,other):
         return self._hash == hash(other)
    def __ne__(self,other):
         return self._hash != hash(other)

numberList = set()

file = open("file.txt", "r")
for line in file:
    x = int(line)
print [perm.original for perm in numberList]

EDIT: even tested it.