Class: NthPermutation::String

Inherits:
Object
  • Object
show all
Defined in:
lib/nth_permutation/string.rb,
ext/nth_permutation/permutation_string.c

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(rb_string) ⇒ Object 



108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
# File 'ext/nth_permutation/permutation_string.c', line 108

static VALUE initialize(VALUE self, VALUE rb_string)
{
    struct Str * str;

    Check_Type(rb_string, T_STRING);
    if(RSTRING_LEN(rb_string) >= LIMIT) rb_raise(rb_eRangeError, "can't handle more than 20 character length string");
    Data_Get_Struct(self, struct Str, str);

    str->ptr = calloc(RSTRING_LEN(rb_string) + 1 , sizeof(char));
    memcpy(str->ptr, StringValuePtr(rb_string), RSTRING_LEN(rb_string));

    str->len = strlen(str->ptr);
    str->factorial = factorial();
    str->frequency = frequency(str->ptr);
    str->possible_permutation = number_of_permutation(str->factorial, str->frequency, str->len);

    rb_iv_set(self, "@str", rb_string);
    rb_iv_set(self, "@length", INT2NUM(RSTRING_LEN(rb_string)));
    rb_iv_set(self, "@possible_permutation", LL2NUM(str->possible_permutation));

    return self;
}

Instance Attribute Details

#length ⇒ Object (readonly)

#possible_permutation ⇒ Object (readonly)

#str ⇒ Object (readonly)

Instance Method Details

#inspect ⇒ Object 



3
4
5
 
# File 'lib/nth_permutation/string.rb', line 3

def inspect
  str
end

#permutation(rb_nth) ⇒ Object 



60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
# File 'ext/nth_permutation/permutation_string.c', line 60

static VALUE permutation(VALUE self, VALUE rb_nth)
{
    struct Str * str;
    Data_Get_Struct(self, struct Str, str);

    Check_Type(rb_nth, T_FIXNUM);
    long long int nth = NUM2LL(rb_nth);
    if(nth > str->possible_permutation) rb_raise(rb_eRangeError, "there's no such nth permutation.");
    if(nth < 0) rb_raise(rb_eRangeError, "negative term of permutation isn't possible.");

    int * freq = (int *) calloc(CHACARTERS, sizeof(int));
    memcpy(freq, str->frequency, CHACARTERS*sizeof(int));

    int len = strlen(str->ptr);

    char * nth_permutation = (char *) calloc(len + 1, sizeof(char));
    int indx = 0;

    while(len)
    {
        long long upto = 0;
        for(int i=0; i<CHACARTERS; i++)
        {
            if(!freq[i])continue;
            freq[i] -= 1;

            long long int now_permutation = number_of_permutation(str->factorial, freq, len-1);
            if(upto + now_permutation >= nth)
            {
                nth -= upto;
                nth_permutation[indx++] = (char) i;
                len--;
                break;
            }
            else
            {
                upto += now_permutation;
                freq[i] += 1;
            }
        }
    }
    nth_permutation[str->len] = NULL;

    free(freq);

    return rb_str_new2(nth_permutation);
}