Factoring ???? [modified]

[Lost User]

This is basic mathematics using an iterative process to check pairs of numbers. What exactly is your programming question; probably homework!

I must get a clever new signature for 2011.

[Johnkokk]

Not homework.I am too old for that now :-D To make things simpler maybe, I've reached to a point that i have limited my list of numbers that can be multiplied betweend them, to numbers which actually have a pottential. So for 160, the program limited the choises to (2,4,5,8,10,20,40) You can see that if you multiply some of them you can come up with 160.For example 2x8x10 or 4x40, etc My programming question is some pointers on how to get this 2x8x10 ? It's probably easy but i am at a point that the mind is frozen :-D Thanks

[Lost User]

Are you seriously saying that you use VB.NET but don't know how to multiply or compare values?

I must get a clever new signature for 2011.

[musefan]

An interesting question... and here is my quick thought... I am assuming the Nx list is in ascending order. first divide A by the first number in Nx (this value becomes your max multiplier) remove all values higher than max multiplier from the list loop each number then loop each remaining number inside the first loop multiply the two and check if it equals A if equals then add to global list if larger then break the loop if smaller then look for another number to multiply (going to need recursion here) ....hmmmm, just re-read and that is not so clear, maybe you will get the gist thou. I may give this a go and post results (but it will be C# thou)

I may or may not be responsible for my own actions

[Johnkokk]

Do you really think, that the problem is to multiply 2 numbers ? :-D I'll take it that i wasn't clear enough maybe. I give you a number A=160 Let's say that i also give you an array, with the following numbers [2,4,5,8,10,20,40] From the numbers in the array, i want to get number A, by multiplying whatever numbers needed. Each number in the array can be used only ONCE. The numbers in the array and also number A can be different each time.It's not always the same. So, for the specific numbers above and using only my mind, i see that 160 can be produced by 2x8x10 or 4x40 or 8x20. It cannot be produced obviously by 2x4x5x8, and so on. So, the problem is to find the algorithm, that can find at least one combination of numbers the can produce A. Sorry if I am not that clear. Thanks anyway.

[Lost User]

Johnkokk wrote:

Do you really think, that the problem is to multiply 2 numbers ?

That's how your question came across, I'm afraid.

Johnkokk wrote:

he problem is to find the algorithm ...

OK, So I suggest you post your question in the Algorithms forum; this has nothing to do with the .NET framework.

I must get a clever new signature for 2011.

[Luc Pattyn]

this is simple when using recursion; what needs to be done is carefully defining the functionality of the recursive method. Hhere is some pseudo-code that should help:

int[] factors=new int[factorList.Length];

// This method should return true if number can be factored using some factors from factorList
// we assume factorList items are all different, positive, non-zero, and ordered numerically ascending.

// call this method with minimum=0 and nesting=0; when it returns true read factors array till the product matches.

public bool CanBeFactoredWithSomeOfThese(int number, List<int> factorList, int minimum, int nesting) {
foreach(int factor in factorList) {
if (factor<=minimum) continue;
if (number%factor!=0) continue;
factors[nesting]=factor;
bool OK=true;
if (number>factor) OK=CanBeFactoredWithSomeOfThese(number/factor, largerFactors, factor, nesting+1);
if (OK) return true;
}
return false;
}

Although combinations aren't examined more than once (that is what minimum is for, we discover factors in ascending order) and it stops on the first solution, this is not quite optimal as it enumerates the factorList way too much. :)

Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.

[Lost User]

Could be simplified, but I think this works (assumes ascending order of integer array)...

    public static void TestFactors()
    {
        List<string> nodes = GetFactors(160, new int\[\] { 2, 3, 4, 5, 6, 7, 8, 10, 15, 20, 25, 30, 40, 50, 100, 500 });
        foreach (string n in nodes)
        {
            Console.WriteLine(n);
        }
        Console.ReadKey();
    }


    private static List<string> GetFactors(int number, int\[\] possValues)
    {
        List<string> nodes = new List<string>();
        for (int j = 0; j < possValues.Count(); j++)
        {
            GetFactorsInner(nodes, number, possValues, j, possValues\[j\], possValues\[j\].ToString());

        }
        return nodes;
    }

    private static void GetFactorsInner(List<string> nodes, int number, int\[\] possValues, int currIndex, int currTot, string currStr)
    {
        for (int i = currIndex + 1; i < possValues.Count(); i++)
        {
            int thisTot = currTot;
            string thisStr = currStr;
            if (thisTot \* possValues\[i\] > number)
            {
                break;
            }
            else if (thisTot \* possValues\[i\] == number)
            {
                thisStr += thisStr == null ? possValues\[i\].ToString() : ", " + possValues\[i\].ToString();
                nodes.Add(thisStr);
                break;
            }
            else if (number % (thisTot \* possValues\[i\]) == 0)
            {
                thisStr += thisStr == null ? possValues\[i\].ToString() : ", " + possValues\[i\].ToString();
                thisTot \*= possValues\[i\];
                GetFactorsInner(nodes, number, possValues, i, thisTot, thisStr);
            }
        }

    }

Output is 2,4,20 2,8,10 4,5,8 4,40 8,20

[Johnkokk]

Thank you very much.That did it exactly.

[Lost User]

You're welcome. There are one or two changes I'd make to that, and one would be to eliminate all numbers that are not factors to start with. If the array was large, it would be an extremely significant reduction in loops. (The first line in the function achieves that).

    private static List<string> GetFactors(int number, int\[\] possValues)
    {
        int\[\] possValuesNew = possValues.Where(i => number % i == 0).ToArray();
        List<string> nodes = new List<string>();
        for (int j = 0; j < possValuesNew.Count(); j++)
        {
            GetFactorsInner(nodes, number, possValuesNew, j, possValuesNew\[j\], possValuesNew\[j\].ToString());

        }
        return nodes;
    }