Asked  8 Months ago    Answers:  5   Viewed   41 times

I'm working on a script that generate some Excel documents and I need to convert a number into its column name equivalent. For example:

1 => A
2 => B
27 => AA
28 => AB
14558 => UMX

I have already written an algorithm to do so, but I'd like to know whether are simpler or faster ways to do it:

function numberToColumnName($number){
    $abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    $abc_len = strlen($abc);

    $result_len = 1; // how much characters the column's name will have
    $pow = 0;
    while( ( $pow += pow($abc_len, $result_len) ) < $number ){
        $result_len++;
    }

    $result = "";
    $next = false;
    // add each character to the result...
    for($i = 1; $i<=$result_len; $i++){
        $index = ($number % $abc_len) - 1; // calculate the module

        // sometimes the index should be decreased by 1
        if( $next || $next = false ){
            $index--;
        }

        // this is the point that will be calculated in the next iteration
        $number = floor($number / strlen($abc));

        // if the index is negative, convert it to positive
        if( $next = ($index < 0) ) {
            $index = $abc_len + $index;
        }

        $result = $abc[$index].$result; // concatenate the letter
    }
    return $result;
}

Do you know a better way to do it? Maybe something to keep it simpler? or a performance improvement?

Edit

ircmaxell's implementation works pretty fine. But, I'm going to add this nice short one:

function num2alpha($n)
{
    for($r = ""; $n >= 0; $n = intval($n / 26) - 1)
        $r = chr($n%26 + 0x41) . $r;
    return $r;
}

 Answers

93

Here's a nice simple recursive function (Based on zero indexed numbers, meaning 0 == A, 1 == B, etc)...

function getNameFromNumber($num) {
    $numeric = $num % 26;
    $letter = chr(65 + $numeric);
    $num2 = intval($num / 26);
    if ($num2 > 0) {
        return getNameFromNumber($num2 - 1) . $letter;
    } else {
        return $letter;
    }
}

And if you want it one indexed (1 == A, etc):

function getNameFromNumber($num) {
    $numeric = ($num - 1) % 26;
    $letter = chr(65 + $numeric);
    $num2 = intval(($num - 1) / 26);
    if ($num2 > 0) {
        return getNameFromNumber($num2) . $letter;
    } else {
        return $letter;
    }
}

Tested with numbers from 0 to 10000...

Wednesday, March 31, 2021
 
NaeiKinDus
answered 8 Months ago
20

Dmitriy is right that you'll want the Sieve of Atkin to generate the prime list but I don't believe that takes care of the whole issue. Now that you have a list of primes you'll need to see how many of those primes act as a divisor (and how often).

Here's some python for the algo Look here and search for "Subject: math - need divisors algorithm". Just count the number of items in the list instead of returning them however.

Here's a Dr. Math that explains what exactly it is you need to do mathematically.

Essentially it boils down to if your number n is:
n = a^x * b^y * c^z
(where a, b, and c are n's prime divisors and x, y, and z are the number of times that divisor is repeated) then the total count for all of the divisors is:
(x + 1) * (y + 1) * (z + 1).

Edit: BTW, to find a,b,c,etc you'll want to do what amounts to a greedy algo if I'm understanding this correctly. Start with your largest prime divisor and multiply it by itself until a further multiplication would exceed the number n. Then move to the next lowest factor and times the previous prime ^ number of times it was multiplied by the current prime and keep multiplying by the prime until the next will exceed n... etc. Keep track of the number of times you multiply the divisors together and apply those numbers into the formula above.

Not 100% sure about my algo description but if that isn't it it's something similar .

Sunday, June 6, 2021
 
zIs
answered 5 Months ago
zIs
44

I would start by introducing some helper methods (factors and square?) to make your code more readable.

Furthermore, I would reduce the number of ranges and arrays to improve memory usage.

require 'prime'

def factors(number)
  [1].tap do |factors|
    primes = number.prime_division.flat_map { |p, e| Array.new(e, p) }
    (1..primes.size).each do |i| 
      primes.combination(i).each do |combination| 
        factor = combination.inject(:*)
        factors << factor unless factors.include?(factor)
      end
    end
  end
end

def square?(number)
  square = Math.sqrt(number)
  square == square.floor
end

def list_squared(m, n)
  (m..n).map do |number|
    sum = factors(number).inject { |sum, x| sum + x ** 2 }
    [number, sum] if square?(sum)
  end.compact
end

list_squared(1, 250)

A benchmark with a narrow range (up to 250) shows only a minor improvement:

require 'benchmark'
n = 1_000

Benchmark.bmbm(15) do |x|
  x.report("original_list_squared :") { n.times do; original_list_squared(1, 250); end }
  x.report("improved_list_squared :") { n.times do; improved_list_squared(1, 250); end }
end

# Rehearsal -----------------------------------------------------------
# original_list_squared :   2.720000   0.010000   2.730000 (  2.741434)
# improved_list_squared :   2.590000   0.000000   2.590000 (  2.604415)
# -------------------------------------------------- total: 5.320000sec

#                               user     system      total        real
# original_list_squared :   2.710000   0.000000   2.710000 (  2.721530)
# improved_list_squared :   2.620000   0.010000   2.630000 (  2.638833)

But a benchmark with a wider range (up to 10000) shows a much better performance than the original implementation:

require 'benchmark'
n = 10

Benchmark.bmbm(15) do |x|
  x.report("original_list_squared :") { n.times do; original_list_squared(1, 10000); end }
  x.report("improved_list_squared :") { n.times do; improved_list_squared(1, 10000); end }
end

# Rehearsal -----------------------------------------------------------
# original_list_squared :  36.400000   0.160000  36.560000 ( 36.860889)
# improved_list_squared :   2.530000   0.000000   2.530000 (  2.540743)
# ------------------------------------------------- total: 39.090000sec

#                               user     system      total        real
# original_list_squared :  36.370000   0.120000  36.490000 ( 36.594130)
# improved_list_squared :   2.560000   0.010000   2.570000 (  2.581622)

tl;dr: The bigger the N the better my code performs compared to the original implementation...

Saturday, August 7, 2021
 
Russ Wheeler
answered 3 Months ago
85

You want to make a best estimate of a probability (or multiple probabilities) and continuously update your estimate as more data become available. That calls for Bayesian inference! Bayesian reasoning is based on the observation that the probability (distribution) of two things, A and B, being the case at the same time is equal to the probability (distribution) of A being the case given that B is the case times the probability that B is the case. In formula form:

P(A,B) = P(A|B)P(B)

and also

P(A,B) = P(B|A)P(A)

and hence

P(A|B)P(B) = P(B|A)P(A)

Take P(B) to the other side and we get the Bayesian update rule:

P(A|B)' = P(B|A)P(A)/P(B)

Usually A stands for whatever variable you are trying to estimate (e.g. "team x beats team y") while B stands for your observations (e.g. the full history of matches won and lost between teams). I wrote the prime (i.e. the quote in P(A|B)') to signify that the left hand of the equation represents an update of your beliefs. To make it concrete, your new estimate of the probability that team x will beat team y, given all observations so far, is the probability of doing those observations given your previous estimate, times your previous estimate, divided by the overall probability of seeing the observations you have seen (i.e. given no assumptions about relative strength between teams; one team winning most of the time is less likely than both teams winning about equally often).

The P(A|B)' from the left hand of the current update becomes the new P(A) on the right hand of the next update. You just keep repeating this as more data come in. Typically, in order to be as unbiased as possible, you start with a completely flat distribution for P(A). Over time P(A) will become more and more certain, although the algorithm is fairly well able to deal with sudden changes of the underlying probability that you're trying to estimate (e.g. if team x suddenly becomes much stronger because a new player joins the team).

The good news is that Bayesian inference works well with the beta distribution which ElKamina also mentioned. In fact the two are often combined in artificial intelligence systems that are meant to learn a probability distribution. While the beta distribution in itself is still an assumption, it has the advantage that it can take many forms (including completely flat and extremely spikey), so there's relatively little reason to be concerned that your choice of distribution might be affecting your outcome.

One piece of bad news is that you still need to make assumptions, apart from the beta distribution. For example, suppose you have the following variables:

A: team x beats team y

B: team y beats team z

C: team x beats team z

and you have observations from direct matches between x and y and from matches between y and z but not from matches between x and z. A simple (though naieve) way to estimate P(C) could be to assume transitivity:

P(C) = P(A)P(B)

Regardless how sophisticated your approach, you'll have to define some kind of structure of probabilities to deal with the gaps as well as the interdependencies in your data. Whatever structure you choose, it will always be an assumption.

Another piece of bad news is that this approach is plain complicated and I cannot give you a full account of how to apply it to your problem. Given that you need a structure of interdependent probabilities (probability of team x beating team y given other distributions involving teams x, y and z), you may want to use a Bayesian network or related analysis (for example a Markov random field or path analysis).

I hope this helps. In any case, feel free to ask for clarifications.

Wednesday, September 22, 2021
 
JackTheKnife
answered 1 Month ago
86

This problem is solvable in polynomial time via the Hungarian algorithm. To get a square matrix, add dummy entries to the shorter list at "distance 0" from everything.

Saturday, October 9, 2021
 
AndiDog
answered 3 Weeks ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :
 
Share