How do I get rid of circular numbers in my list

问题:

Okay, I know that this code is crude, and all around a messy, but I am no programmer, so bear with me. I have this code that lists a bunch of numbers, but I want it to not list any circular copies of the numbers.

For example, if the number 111262 is on my list, I don't want 112621, 126211, 262111, 621112, or 211126 to be listed.

Sorry, that number cannot be on the list.

For a true example, if the number 111252 is on my list, I don't want 112521, 125211, 252111, 521112, or 211125 to be listed.

Any help is appreciated!

namespace Toric_Classes
{
class Program
{
    static void Main(string[] args)
    {
        int number_of_perms=0;
        bool badsubsum1;
        bool badsubsum2;
        int subsum1 = 0;
        int subsum2 = 0;
        int sum = 0;
        int class_length=6;
        int[] toric_class=new int[class_length];
        // The nested for loops scroll through every possible number of length class_length, where each digit can have a value of 1,2,..., or class_length-1
        // Each number is looked at as an array, and is not stored anywhere, only printed if it satisfies certain conditions
        for(int i1=1; i1<class_length; i1++)
        {
            toric_class[0] = i1;
            for (int i2 = 1; i2 < class_length; i2++)
            {
                toric_class[1] = i2;
                for (int i3 = 1; i3 < class_length; i3++)
                {
                    toric_class[2] = i3;
                    for (int i4 = 1; i4 < class_length; i4++)
                    {
                        toric_class[3] = i4;
                        for (int i5 = 1; i5 < class_length; i5++)
                        {
                            toric_class[4] = i5;
                            for (int i6 = 1; i6 < class_length; i6++)
                            {
                                badsubsum1 = false;
                                badsubsum2 = false;
                                toric_class[5] = i6;
                                // Find the value of the sum of the digits of our array.
                                // We only want numbers that have a total digit sum being a multiple of class_length
                                for (int k = 0; k < class_length; k++)
                                {
                                    sum += toric_class[k];
                                }
                                // The follwong two nested loops find the value of every contiguous subsum of our number, but not the total subsum.
                                // We *do not* want any subsum to be a multiple of class_length.
                                // That is, if our number is, say, 121342, we want to find 1+2, 1+2+1, 1+2+1+3, 1+2+1+3+4, 2+1, 2+1+3, 2+1+3+4, 2+1+3+4+2, 1+3, 1+3+4, 1+3+4+2, 3+4, 3+4+2, and 4+2
                                // The following checks 1+2, 1+2+1, 1+2+1+3, 1+2+1+3+4, 2+1, 2+1+3, 2+1+3+4, 1+3, 1+3+4, and 3+4
                                for (int i = 0; i < class_length - 1; i++)
                                {
                                    for (int j = i + 1; j < class_length - 1; j++)
                                    {
                                        for (int k = i; k < j; k++)
                                        {
                                            subsum1 += toric_class[k];
                                        }
                                        if (subsum1 % class_length == 0)
                                        {
                                            badsubsum1 = true;
                                            break;
                                        }
                                        subsum1 = 0;
                                    }
                                }
                                // The following checks 2+1, 2+1+3, 2+1+3+4, 2+1+3+4+2, 1+3, 1+3+4, 1+3+4+2, 3+4, 3+4+2, and 4+2
                                for (int i = 1; i < class_length; i++)
                                {
                                    for (int j = i + 1; j < class_length; j++)
                                    {
                                        for (int k = i; k < j; k++)
                                        {
                                            subsum2 += toric_class[k];
                                        }
                                        if (subsum2 % class_length == 0)
                                        {
                                            badsubsum2 = true;
                                            break;
                                        }
                                        subsum2 = 0;
                                    }
                                }
                                // We only want numbers that satisfies the following conditions
                                if (sum % class_length == 0 && badsubsum1 == false && badsubsum2 == false)
                                {
                                    foreach (var item in toric_class)
                                    {
                                        Console.Write(item.ToString());
                                    }
                                    Console.Write(Environment.NewLine);
                                    number_of_perms++;
                                }
                                sum = 0;
                                subsum1 = 0;
                                subsum2 = 0;

                            }
                        }
                    }
                }
            }
        }
        Console.WriteLine("Number of Permuatations: "+number_of_perms);
        Console.Read();
    }
}
}

EDIT

To clarify, I am creating a list of all numbers with length n that satisfy certain conditions. Consider the number d1d2...dn, where each di is a digit of our number. Each di may have value 1,2,...,n. Our number is in the list if it satisfies the following

1. The sum of all the digits is a multiple of n, that is,

   d1+d2+...+dn = 0 mod n

2. Every contiguous subsum of the digits is not a multiple of n, aside from the total sum, that is, if i !=1 and j != n, then

   di+d(i+1)+...+dj != 0 mod n

I should mention again that a "number" does not strictly use the numbers 0-9 in its digits. It may take any value between 1 and n. In my code, I am using the case where n=6.

The code works by creating an array of length class_length (in the code above, I use class_length=6). We first have 6 nested for loops that simply assign values to the array toric_class. The first for assigns toric_class[0], the second for assigns toric_class[1], and so on. In the first go around, we are generating the array 111111, then 111112, up to 111115, then 111121, etc. So essentially, we are looking at all heximal numbers that do not include 0. Once we reach our sixth value in our array, we check the array toric_class and check its values to ensure that it satisfies the above conditions. If it does, we simply print the array in a line, and move on.

回答1:

Here is my easy and inefficient way that should work with minimal changes to your code. It requires shared string list var strList = new List<string>(); to store the used numbers. Then this part:

foreach (var item in toric_class)
{
    Console.Write(item.ToString());
}
Console.Write(Environment.NewLine);
number_of_perms++; 

becomes something like this:

string strItem = " " + string.Join(" ", toric_class) + " "; // Example: int[] {1, 12, 123} becomes " 1 12 123 "

if (!strList.Any(str => str.Contains(strItem))) // Example: if " 1 12 123 1 12 123 " contains " 1 12 123 "
{
    Console.WriteLine(strItem);

    strItem += strItem.Substring(1); // double the string, but keep only one space between them
    strList.Add(strItem);
}

number_of_perms++; // not sure if this should be in the if statement

---

The idea is that for example the string " 1 1 1 2 5 2 1 1 1 2 5 2 " contains all circular copies of the numbers {1, 1, 1, 2, 5, 2}. I used string as a lazy way to check if array contains sub-array, but you can use similar approach to store copy of the used numbers in a list of arrays new List<int[]>() and check if any of the arrays in the list is circular copy of the current array, or even better HashSet<int[]>() approach similar to @slavanap's answer.

---

The first version of my answer was the easiest, but it works only with array of single digit items.

List is almost the same as array (new List<string>() instead of new string[]), but makes it much easier and efficient to add items to it. For example {1,2}.Add(3) becomes {1,2,3}.

str => str.Contains(strItem) is shortcut for a function that accepts parameter str and returns the result of str.Contains(strItem). That "function" is then passed to the .Any LINQ extension, so

strList.Any(str => str.Contains(strItem))

is shortcut for something like this:

foreach(string str in strList)
{
    if (str.Contains(strItem)) 
    {
        return true;
    }
}
return false;

回答2:

The following method:

private static List<int> GetCircularEquivalents(int value)
{
    var circularList = new List<int>();
    var valueString = value.ToString();
    var length = valueString.Length - 1;

    for (var i = 0; i < length; i++)
    {
        valueString = valueString.Substring(1, length) + valueString.Substring(0, 1);
        circularList.Add(int.Parse(valueString));
    }

    return circularList;
}

will return a list of the circular numbers derived from the input value. Using your example, this method can be called like this:

var circularList = GetCircularEquivalents(111262);
var dirtyList = new List<int> { 1, 112621, 2, 126211, 3, 262111, 4, 621112, 5, 211126, 6 };
var cleanList = dirtyList.Except(circularList).ToList();

which would result in a cleanList made up of the numbers 1 through 6, i.e. the dirtyList with all the circular numbers derived from 111262 removed.

回答3:

That's where OOP really benefits. Comments inlined.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication3 {

    struct MyInt : IEquatable<MyInt> {
        private int _value;

        public MyInt(int value) {
            _value = value;
        }

        // make it look like int
        static public implicit operator MyInt(int value) {
            return new MyInt(value);
        }
        public static explicit operator int(MyInt instance) {
            return instance._value;
        }

        // main difference in these 3 methods
        private int GetDigitsNum() {
            int temp, res;
            for (res = 0, temp = Math.Abs(_value); temp > 0; ++res, temp /= 10);
            return res;
        }
        public bool Equals(MyInt other) {
            int digits = other.GetDigitsNum();
            if (digits != this.GetDigitsNum())
                return false;
            int temp = other._value;

            // prepare mul used in shifts
            int mul = 1;
            for (int i = 0; i < digits - 1; ++i)
                mul *= 10;

            // compare
            for (int i = 0; i < digits; ++i) {
                if (temp == _value)
                    return true;
                // ROR
                int t = temp % 10;
                temp = temp / 10 + t * mul;
            }
            return false;
        }
        public override int GetHashCode() {
            // hash code must be equal for "equal" items,
            // that's why use a sum of digits.
            int sum = 0;
            for (int temp = _value; temp > 0; temp /= 10)
                sum += temp % 10;
            return sum;
        }

        // be consistent
        public override bool Equals(object obj) {
            return (obj is MyInt) ? Equals((MyInt)obj) : false;
        }
        public override string ToString() {
            return _value.ToString();
        }
    }

    class Program {
        static void Main(string[] args) {

            List<MyInt> list = new List<MyInt> { 112621, 126211, 262111, 621112, 211126 };
            // make a set of unique items from list
            HashSet<MyInt> set = new HashSet<MyInt>(list);

            // print that set    
            foreach(int item in set)
                Console.WriteLine(item);

        }
    }
}

Output: 112621