Making a function more efficient

[CatorCanulis]

Hi everyone,

I'm working on a function that avoids transposed numbers. Like if you have 12 you can't have 21 or if you have 126 you can't have 216 oder 621.

What I got so far:

#!/bin/env python3

import itertools
import itertools

from numba import jit, cuda
import numpy as np

#@jit(target_backend='cuda')
def getNonSwappables(iStart, iStop, verbose = False):

  idsClean = []

  ids = list(range(iStart, iStop))

  for i in ids:

    if verbose:
      print("Processing: ", i)
    # Create permutation for current string.
    sPermutations = [''.join(p) for p in itertools.permutations(str(i))]

    # Check if the clean ids list contains any of the permutations.
    if not any(item in str(idsClean) for item in sPermutations):

      # If not so, apped the current integer to the list of clean ids.
      idsClean.append(i)

  return(idsClean)

listIDsClean = getNonSwappables(1, 100000, True)
print(listIDsClean)
print(len(listIDsClean))

For numbers < 10.000 it works somewhat reasonable. But larger numbers take forever. Is there a way I can code this more efficient?

As you can see, I already tried to crunch it with my gpu but compilation failed. That's not really a sustainable option anyway.

Any help is greatly appreciated.

Markus

[Gribouillis]

Here is a possible solution

from more_itertools import unique_everseen

def non_swappable(start, stop):

    def our_key(n):
        return ''.join(sorted(str(n)))

    return unique_everseen(range(start, stop), key=our_key)

def main():
    res = list(non_swappable(0, 1000))
    print(res)

if __name__ == '__main__':
    main()

Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 33, 34, 35, 36, 37, 38, 39, 40, 44, 45, 46, 47, 48, 49, 50, 55, 56, 57, 58, 59, 60, 66, 67, 68, 69, 70, 77, 78, 79, 80, 88, 89, 90, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 111, 112, 113, 114, 115, 116, 117, 118, 119, 122, 123, 124, 125, 126, 127, 128, 129, 133, 134, 135, 136, 137, 138, 139, 144, 145, 146, 147, 148, 149, 155, 156, 157, 158, 159, 166, 167, 168, 169, 177, 178, 179, 188, 189, 199, 200, 202, 203, 204, 205, 206, 207, 208, 209, 222, 223, 224, 225, 226, 227, 228, 229, 233, 234, 235, 236, 237, 238, 239, 244, 245, 246, 247, 248, 249, 255, 256, 257, 258, 259, 266, 267, 268, 269, 277, 278, 279, 288, 289, 299, 300, 303, 304, 305, 306, 307, 308, 309, 333, 334, 335, 336, 337, 338, 339, 344, 345, 346, 347, 348, 349, 355, 356, 357, 358, 359, 366, 367, 368, 369, 377, 378, 379, 388, 389, 399, 400, 404, 405, 406, 407, 408, 409, 444, 445, 446, 447, 448, 449, 455, 456, 457, 458, 459, 466, 467, 468, 469, 477, 478, 479, 488, 489, 499, 500, 505, 506, 507, 508, 509, 555, 556, 557, 558, 559, 566, 567, 568, 569, 577, 578, 579, 588, 589, 599, 600, 606, 607, 608, 609, 666, 667, 668, 669, 677, 678, 679, 688, 689, 699, 700, 707, 708, 709, 777, 778, 779, 788, 789, 799, 800, 808, 809, 888, 889, 899, 900, 909, 999]

[DPaul]

Always on the lookout for an interesting challenge, it's been a while.
Would this do ?

uniques = []
for x in range (1,1001):
    lst = list(str(x))
    lst.sort()
    if not lst in uniques:
        uniques.append(lst)
        print(x)

Paul

[Gribouillis]

As an exercise, I wrote code to check whether an integer n is in the swappable list between start and stop but without computing the sequence. That is to say the code determines if an integer is in the sequence without allocating memory to store the whole sequence as unique_everseen() or @DPaul 's code does. For example it can be used to tell if a number with 1000 digits is in the list between two huge numbers.

class Finder:
    def __init__(self, start):
        assert isinstance(start, int) and start >= 0
        self.start = start
        self.digits = [int(d) for d in str(start)]
        self.ndigits = len(self.digits)

    def find_swap(self, n):
        """Finds the smallest permutation of n which is >= self.start.

        Raise ValueError if there is no such permutation

            >>> f = Finder(374676636447)
            >>> f.find_swap(982364788871)
            374678128889
        """
        assert isinstance(n, int) and n >= 0
        sn = str(n)
        if len(sn) == self.ndigits:
            buffer = [0] * self.ndigits
            freq = [0] * 10
            for d in sn:
                freq[int(d)] += 1
            for k, x in enumerate(self.digits):
                if freq[x]:
                    buffer[k] = x
                    freq[x] -= 1
                else:
                    while True:
                        for y in range(x+1, 10):
                            if freq[y]:
                                buffer[k] = y
                                freq[y] -= 1
                                p = k + 1
                                for z, f in enumerate(freq):
                                    for i in range(f):
                                        buffer[p] = z
                                        p += 1
                                return int(''.join(str(d) for d in buffer))
                        else:
                            k -= 1
                            if k < 0:
                                raise ValueError(n)
                            freq[buffer[k]] += 1
                            buffer[k] = 0
                            x = self.digits[k]
                    else:
                        raise ValueError(n)
        elif len(sn) < self.ndigits:
            raise ValueError(n)
        elif len(sn) > self.ndigits:
            seq = sorted(sn)
            for i, v in enumerate(seq):
                if v != '0':
                    seq[0], seq[i] = seq[i], seq[0]
                    return int(''.join(seq))

def is_swappable(start, stop, n):
    """Return true if n is in the swappable sequence from start to stop
    """
    assert start <= stop
    try:
        k = Finder(start).find_swap(n)
    except ValueError:
        return False
    return k == n and k < stop

def main():
    start = 374676636447
    f = Finder(start)
    print(f.find_swap(982364788871))

    print(is_swappable(0, 1000, 354)) # prints false

if __name__ == '__main__':
    main()

Output:
374678128889
False

[DPaul]

@Gribouillis: Impressed by your solution, I do not wish to rain on your parade, but
a solution without storing the whole sequence is also possible in the KISS department.

for x in range (1,1001):
    swapper = False
    for y in range(1, x):
        lstX = list(str(x))
        lstX.sort()
        lstY = list(str(y))
        lstY.sort()
        if lstX == lstY:
            swapper = True
            break           
    if not swapper:
        print(x)

Further improvements could be made if I take into account that
1 digit numbers only have to be compared with other 1 digits, 2 digits with 2, etc.
No point in comparing 2 digit numbers with 3.
Paul

[Gribouillis]

a solution without storing the whole sequence is also possible in the KISS department.

It is simple and it uses little memory, but it also uses a huge amount of time. Suppose that 'start', 'stop' and 'x' have 1000 digits each. Will your code tell if x is in the list?

[CatorCanulis]

All of the solutions are indeed very impressive! My raspberry pi 4 crunches it like it was nothing. I tried to adapt Gribouillis function to find the next possible, non swappable number after a given maximum but failed. I feel like this should be possible by changing the maximum of the range ...

[DPaul]

Suppose that 'start', 'stop' and 'x' have 1000 digits each. Will your code tell if x is in the list?

Touché !
But if TS is happy, that's all that matters.
Paul

[Pedroski55]

I was interested, so I thought I'd try!

As I see it, the problem is simply, rearrange all numbers to find the smallest possible number using those digits.

Thus, 101 can't be made smaller, but 110 would become 101, 1100 becomes 1001

If the rearranged number is in the list, it won't be added.

#! /usr/bin/python3
from time import time

unums = {i:[10**(i-1)] for i in range(2, 6)}

# from a given number rearrange it to create the smallest number using those digits
def makeSmall(num):
    templist = []
    for j in num:
        templist.append(j)
    smallest = '9'
    for j in range(len(templist)):        
        if not templist[j] == '0':
            if templist[j] < smallest:
                smallest = templist[j]
                #print('smallest number is', smallest)
    newlist = []
    count = 0
    # how many times is the smallest number present?
    for j in templist:
        if j == smallest:
            count += 1
    for j in range(count - 1):
        newlist.append(smallest)
    for j in templist:    
        if not j == smallest:
            newlist.append(j)
    newlist.sort()
    #print(newlist)
    newnewlist = [smallest] + newlist
    #print(newnewlist)
    numstring = ''.join(newnewlist)
    return int(numstring)

def getNums(start):
    key = len(str(start))
    print('key is', key)
    for i in range(start + 1, start * 10):
        numstring = str(i)
        mynum = makeSmall(numstring)
        if not mynum in unums[key]:
            unums[key].append(mynum)
def doit():
    for key in unums.keys():
        getNums(unums[key][0])
        #unums[key].sort()
 
if __name__ == '__main__':
    start = time()
    doit()    
    path2text = '/home/pedro/myPython/sets/'
    with open(path2text + 'unique_numbers.txt', 'w') as result:
        for key in unums.keys():
            stringlist = []
            for d in unums[key]:
                stringlist.append(str(d)+ '\n')               
            data = ''.join(stringlist)
            result.write(data)
        print('Result saved to', path2text + 'unique_numbers.txt')
    end = time()
    execution_time = end - start        
    print('Execution time was:', execution_time)

Output:
pedro@pedro-HP:~/myPython/sets$ ./find_unique_number_groups5.py
key is 2
key is 3
key is 4
key is 5
Execution time was: 0.6043331623077393
pedro@pedro-HP:~/myPython/sets$ 

[DPaul]

As I see it, the problem is simply, rearrange all numbers to find the smallest possible number using those digits.

I find your idea interesting, but at first glance, the program does not score well in the speed department (like mine).

I thought that a faster KISS alternative is lurking in the shadows, something along the lines of "early elimination"
of possibilities:
- Only compare numbers with equal number of digits.
- Only compare numbers with identical sums of digits.
Paul